AT_abc010_4 [ABC010D] 浮気予防

[problemUrl]: https://atcoder.jp/contests/abc010/tasks/abc010_4 高橋君の秘書のなぎさちゃんは、高橋君が大好きです。今日も、高橋君に悪い虫が取り憑かないように、高橋君を監視しなければなりません。 高橋君は、女の子と仲良くなるために、自前の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 $ であることが保障されている。

なぎさちゃんが工作を行う必要のある回数の最小値を、 $ 1 $ 行で出力せよ。出力の末尾には改行をいれること。

### 部分点 $ 0\ ≦\ E\ ≦\ 12 $ を満たすテストケースに正解した場合、部分点として $ 99 $ 点が与えられる。 ### Sample Explanation 1 !\[\](/img/abc/010/pic1.png) 図のように、 $ 1 $ つの友人関係を解消するだけで、$ 2 $ 人の女の子を高橋君から切り離すことが出来ます。 ### Sample Explanation 2 !\[\](/img/abc/010/pic2.png) マークしている女の子は一人だけなので、この人をログイン出来なくするだけで、目的を達成することができます。 ### Sample Explanation 3 !\[\](/img/abc/010/pic3.png) 図のように工作を行うことで、全ての女の子に対して工作を行えます。 ### Sample Explanation 4 IDが $ 3 $ の人をログイン出来ないようにしても、高橋君が友達を探すのに影響がないことに注意してください。 ### Sample Explanation 5 高橋君には友達がいないため、工作を行う必要はありません。