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
この場合は一本も青色の辺を追加することができない。