AT_arc049_c [ARC049C] ぬりまーす

[problemUrl]: https://atcoder.jp/contests/arc049/tasks/arc049_c 高橋君は大会の上位入賞の特典として旅行に行ったときに、「ぬりまーす」という絵の具を買いました。 また、高橋君の手元には $ 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) $ が空白区切りで与えられる。 - その制約の下では決して塗ることができない頂点が発生するような制約の組み合わせが与えられる可能性がある。また、複数同じ制約が与えられる可能性もある。

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

### Sample Explanation 1 頂点3→頂点2→頂点1の順に色を塗れば良いです。 ### Sample Explanation 2 この制約下では、頂点1を塗ることはできません。 ### Sample Explanation 3 この制約の下では、どの頂点にも色を塗ることはできません。