C - 噂の拡散 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 366 点

問題文

高橋君は、とある学校の生徒会長です。文化祭の準備期間中に、ある重要な連絡事項を生徒たちに伝える必要があります。

この学校には N 人の生徒がおり、各生徒には 1 から N までの番号が付けられています。

生徒同士の友人関係が M 組与えられます。友人関係は双方向であり、自己ループや多重辺はありません。

高橋君は最初に K 人の生徒を選び、彼らに直接情報を伝えました。最初に情報を伝えた K 人の生徒の番号を S_1, S_2, \ldots, S_K とします。

情報は友人関係を通じて次々と伝わっていきます。すなわち、情報を知っている生徒の友人もその情報を知り、さらにその友人にも伝わる、ということが繰り返されます。より正確には、S_1, S_2, \ldots, S_K のいずれかの生徒から、友人関係の辺を 0 回以上たどって到達できる生徒はすべて最終的に情報を知ることになります。

最終的に情報を知っている生徒の人数を求めてください。なお、最初に情報を伝えられた K 人の生徒自身も、情報を知っている生徒に含みます。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq K \leq N
  • 1 \leq S_i \leq N (1 \leq i \leq K)
  • S_i \neq S_j (i \neq j)
  • 1 \leq u_i < v_i \leq N (1 \leq i \leq M)
  • (u_i, v_i) \neq (u_j, v_j) (i \neq j)
  • 入力はすべて整数

入力

N M K
S_1 S_2 \ldots S_K
u_1 v_1
u_2 v_2
\vdots
u_M v_M
  • 1 行目には、生徒の人数を表す N 、友人関係の数を表す M 、最初に情報を伝えた生徒の人数を表す K が、スペース区切りで与えられる。
  • 2 行目には、最初に情報を伝えた生徒の番号 S_1, S_2, \ldots, S_K が、スペース区切りで与えられる。
  • 3 行目から M + 2 行目には、友人関係が M 行で与えられる。
  • 2 + i 行目 (1 \leq i \leq M) には、 i 番目の友人関係における 2 人の生徒の番号 u_i と v_i がスペース区切りで与えられる。この友人関係は双方向である。各辺は u_i < v_i を満たす形で与えられる。

出力

最終的に情報を知っている生徒の人数を 1 行で出力せよ。

入力例 1

5 4 1
1
1 2
2 3
3 4
1 5

出力例 1

5

入力例 2

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

出力例 2

7

入力例 3

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

出力例 3

10

Score : 366 pts

Problem Statement

Takahashi is the student council president of a certain school. During the preparation period for the cultural festival, he needs to convey an important announcement to the students.

There are N students in this school, and each student is assigned a number from 1 to N.

M pairs of friendship relations between students are given. Friendships are bidirectional, and there are no self-loops or multiple edges.

Takahashi initially chose K students and directly informed them. Let the numbers of the K students who were initially informed be S_1, S_2, \ldots, S_K.

Information spreads successively through friendship relations. That is, friends of students who know the information also learn it, and it further spreads to their friends, and so on. More precisely, all students who can be reached from any of the students S_1, S_2, \ldots, S_K by following zero or more friendship edges will eventually learn the information.

Find the number of students who ultimately know the information. Note that the K students who were initially informed are also counted as students who know the information.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq K \leq N
  • 1 \leq S_i \leq N (1 \leq i \leq K)
  • S_i \neq S_j (i \neq j)
  • 1 \leq u_i < v_i \leq N (1 \leq i \leq M)
  • (u_i, v_i) \neq (u_j, v_j) (i \neq j)
  • All input values are integers

Input

N M K
S_1 S_2 \ldots S_K
u_1 v_1
u_2 v_2
\vdots
u_M v_M
  • The first line contains N representing the number of students, M representing the number of friendships, and K representing the number of students initially informed, separated by spaces.
  • The second line contains the numbers S_1, S_2, \ldots, S_K of the students initially informed, separated by spaces.
  • From the 3rd line to the (M + 2)-th line, M friendships are given over M lines.
  • The (2 + i)-th line (1 \leq i \leq M) contains the numbers u_i and v_i of the two students in the i-th friendship, separated by a space. This friendship is bidirectional. Each edge is given in a form satisfying u_i < v_i.

Output

Output the number of students who ultimately know the information in a single line.

Sample Input 1

5 4 1
1
1 2
2 3
3 4
1 5

Sample Output 1

5

Sample Input 2

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

Sample Output 2

7

Sample Input 3

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

Sample Output 3

10