C - ぬりまーす Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君は大会の上位入賞の特典として旅行に行ったときに、「ぬりまーす」という絵の具を買いました。

また、高橋君の手元には N 頂点の有向グラフがあり、グラフの各頂点は 頂点 1, 頂点 2, ..., 頂点 N と表されます。

高橋君は色を塗るのが大好きなので、その「ぬりまーす」を使い、手元の有向グラフの頂点に色を塗って遊ぼうと思っています。 ただし、適当に色を塗っても面白くないので、いくつかの頂点の間に以下のような制約がある条件下で色を塗ります。

  • タイプ1: ある頂点 x に色を塗るとき、既に頂点 y に色が塗られてなければならない。
  • タイプ2: ある頂点 u に色を塗るとき、既に頂点 v に色が塗られていてはいけない。

タイプ1の制約の個数は A 個で、タイプ2の制約の個数は B 個です。

最初はどの頂点にも色は塗られていません。 あなたの仕事は、適切な順番でグラフの頂点に色を塗り、最終的に色が塗られている最大の頂点数を求めることです。

入力

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

N
A
x_1 y_1
x_2 y_2
:
x_A y_A
B
u_1 v_1
u_2 v_2
:
u_B v_B
  • 1 行目には、グラフの頂点の数を表す整数 N (1≦N≦100) が与えられる。
  • 2 行目には、タイプ1の制約の個数を表す整数 A (0≦A≦100) が与えられる。
  • 3 行目からの A 行には、タイプ1の制約の情報が与えられる。そのうち i (1≦i≦A) 行目には、「ある頂点 x_i に色を塗るとき、既に頂点 y_i に色が塗られてなければならない。」という制約を表す 2 つの整数 x_i,y_i(1≦x_i,y_i≦N,x_i≠y_i) が空白区切りで与えられる。
  • 3+A 行目には、タイプ2の制約の個数を表す整数 B (0≦B≦10) が与えられる。
  • 3+A+1 行目からの B 行には、タイプ2の制約の情報が与えられる。そのうち i (1≦i≦B) 行目には、「ある頂点 u_i に色を塗るとき、既に頂点 v_i に色が塗られていてはいけない。」という制約を表す 2 つの整数 u_i,v_i(1≦u_i,v_i≦N,u_i≠v_i) が空白区切りで与えられる。
  • その制約の下では決して塗ることができない頂点が発生するような制約の組み合わせが与えられる可能性がある。また、複数同じ制約が与えられる可能性もある。

出力

最終的に色が塗られる頂点数の最大値を出力せよ。出力の末尾には改行を入れること。

入力例 1

3
2
1 2
2 3
1
3 1

出力例 1

3

頂点3→頂点2→頂点1の順に色を塗れば良いです。

入力例 2

3
2
1 2
2 3
1
1 3

出力例 2

2

この制約下では、頂点1を塗ることはできません。

入力例 3

3
3
1 2
2 3
3 1
0

出力例 3

0

この制約の下では、どの頂点にも色を塗ることはできません。

入力例 4

9
7
1 2
1 3
5 4
8 5
9 8
6 1
7 1
2
1 4
4 1

出力例 4

6

入力例 5

100
0
0

出力例 5

100