実行時間制限: 2 sec / メモリ制限: 256 MB
問題文
高橋君の秘書のなぎさちゃんは、高橋君が大好きです。今日も、高橋君に悪い虫が取り憑かないように、高橋君を監視しなければなりません。
高橋君は、女の子と仲良くなるために、自前のSNSを使います。SNSで友人関係にある人を辿って行き、見つけた女の子にメッセージを送ります。 なぎさちゃんは、高橋君のメッセージを女の子が見ることがないように、このSNSに対して、工作を行うことにしました。
行える工作活動は、以下の 2つです。
- 特定の二人の友人関係を解消する
- 特定の一人のパスワードを変え、ログイン出来なくする 高橋君のパスワードは変更できません。(21:11追記)
友人関係が解消されると、高橋君は、その二人の間を辿ることが出来なくなります。しかし、他の友人を経由して、辿ることが可能な場合は、その限りではありません。
パスワードを変更すると、その人は、メッセージを見ることが不可能になります。友人関係に変化はないので、パスワードを変更された人を辿って、別の友人を探すのは可能です。
なぎさちゃんは、出来るだけ工作の回数を少なくして、予めマークした女の子達が、高橋君のメッセージを閲覧できないようにしたいです。なぎさちゃんが工作を行う必要のある回数を求めてください。
入力
入力は以下の形式で標準入力から与えられる。
N G E p_1 p_2 ... p_G a_1 b_1 a_2 b_2 : a_E b_E
- 1 行目には、SNSの登録人数を表す整数 N (1 ≦ N ≦ 100) と、なぎさちゃんがマークしている女の子の数 G (0 ≦ G ≦ N - 1)、 SNSの友人関係の数を表す整数 E (0 ≦ E ≦ N × (N-1) / 2)がスペース区切りで与えられる。
- 2 行目では、なぎさちゃんがマークしている i 番目の女の子のIDを表す整数 p_i (1 ≦ p_i ≦ N - 1) の値が、スペース区切りで G 個与えられる。
- 3 行目から E 行では、友人関係に関する情報が与えられる。このうち i 行目では i 番目の友人関係における、二人のID番号を表す 2 つの整数 a_i (0 ≦ a_i ≦ N - 1) b_i (0 ≦ b_i ≦ N - 1) の値が、スペース区切りで与えられる。
- i ≠ j のとき、a_i = a_j かつ b_i = b_j、または a_i = b_j かつ b_i = a_j になることはないことが保障されている。
- 全ての入力において、高橋君のIDは 0 であることが保障されている。
部分点
0 ≦ E ≦ 12 を満たすテストケースに正解した場合、部分点として 99 点が与えられる。
出力
なぎさちゃんが工作を行う必要のある回数の最小値を、 1 行で出力せよ。出力の末尾には改行をいれること。
入力例1
4 2 3 2 3 0 1 1 2 1 3
出力例1
1
図のように、 1 つの友人関係を解消するだけで、2 人の女の子を高橋君から切り離すことが出来ます。
入力例2
4 1 4 3 0 1 0 2 1 3 2 3
出力例2
1
マークしている女の子は一人だけなので、この人をログイン出来なくするだけで、目的を達成することができます。
入力例3
10 3 11 7 8 9 0 1 0 2 0 3 0 4 1 5 2 5 5 6 6 7 6 8 3 9 4 9
出力例3
2
図のように工作を行うことで、全ての女の子に対して工作を行えます。
入力例4
6 2 6 4 5 0 1 0 2 1 3 2 3 3 4 3 5
出力例4
2
IDが 3 の人をログイン出来ないようにしても、高橋君が友達を探すのに影響がないことに注意してください。
入力例5
4 3 3 1 2 3 1 2 1 3 2 3
出力例5
0
高橋君には友達がいないため、工作を行う必要はありません。