L - グラフ色ぬり Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

N 頂点 A+B 辺からなる単純有向グラフ G が与えられます。頂点には 1,\ 2,\ …,\ N の番号が振られています。

このグラフは、辺のうち A 本が赤色に、残りの B 本が青色に塗られています。

ここから青色の辺を全て削除したグラフを G' とします。

以下の条件を満たすグラフ G'' のうち、辺数の最大は何本かを求めてください。

  • G'' は G から、青色の辺を 0 本以上任意の本数選び、削除したものである。
  • 頂点 1 を始点、頂点 N を終点としたときの G' と G'' の最大流の値が等しい。ただし辺の容量は全て 1 とする。

最大流についてはここを参考にすること。

入力

入力は以下の形式で標準入力から与えられる。

N A B
X_1 Y_1
X_2 Y_2
:
X_{A+B} Y_{A+B}
  • 1 行目には整数 N(2 \leq N \leq 100)、A(1 \leq A \leq 200)、B(1 \leq B \leq 200) が空白区切りで与えられる。
  • そのあと A+B 行には、グラフの辺の情報が与えられる。このうち i 行目には整数 X_i(1 \leq X_i \leq N),\ Y_i(1 \leq Y_i \leq N) が空白区切りで与えられ、これは辺 (X_i,\ Y_i) が存在することを表す。
  • (X_1,\ Y_1), (X_2,\ Y_2), …,(X_A,\ Y_A) は赤く塗られた辺であり、(X_{A+1},\ Y_{A+1}), (X_{A+2},\ Y_{A+2}), ..., (X_{A+B},\ Y_{A+B}) は青く塗られた辺である。
  • X_i = Y_i なる i は存在しない。また、i \neq j ならば、Y_i \neq Y_j または X_i \neq X_j を満たす。

出力

G'' の辺数の最大を出力せよ。出力は標準出力に行い、末尾に改行を入れること。

入力例1

4 2 2
1 2
2 4
1 3
3 4

出力例1

3

入力例2

4 2 2
1 2
3 4
1 3
2 4

出力例2

2

入力例3

5 3 4
1 2
2 3
3 5
1 4
2 4
3 4
5 4

出力例3

7

この場合すべての青色の辺を追加することができる。

入力例4

5 1 3
1 5
2 3
3 4
4 2

出力例4

4

この場合もすべての青色の辺を追加することができる。

入力例5

5 3 4 
1 2
2 3
3 4
1 5
2 5
3 5
4 5

出力例5

3

この場合は一本も青色の辺を追加することができない。