C - Spread of Rumors Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君の学校には N 人の生徒がおり、生徒には 1 から N までの番号が付けられています。生徒同士の友人関係が M 個与えられ、i 番目の友人関係は生徒 u_i と生徒 v_i が互いに友人であることを表します（友人関係は双方向です）。なお、同じ友人関係が複数回与えられることや、ある生徒が自分自身と友人であるような関係は存在しません。

はじめに、K 人の生徒 C_1, C_2, \ldots, C_K だけがある噂を知っている状態です。この初期状態から、噂は次のルールに従って日ごとに広がります。

> 判定： 各日の開始時点で、まだ噂を知らない生徒それぞれについて、その生徒の友人のうち噂を知っている人数を数えます。この人数が T 人以上であれば、その生徒はその日の終わりに新たに噂を知ります。

>

> 同時更新： その日に新たに噂を知る生徒が複数いる場合、それらは全員同時にその日の終わりに噂を知ります。ある生徒がその日の終わりに新たに噂を知ったとしても、それは同じ日の他の生徒の判定には影響しません。

この過程を、新たに噂を知る生徒がいなくなるまで毎日繰り返します。

最終的に噂を知っている生徒の人数を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq K \leq N
  • 1 \leq T \leq N
  • 1 \leq C_i \leq N (1 \leq i \leq K)
  • C_i はすべて異なる
  • 1 \leq u_i < v_i \leq N (1 \leq i \leq M)
  • (u_i, v_i) の組はすべて異なる
  • 入力はすべて整数

入力

N M K T
C_1 C_2 \ldots C_K
u_1 v_1
u_2 v_2
\vdots
u_M v_M
  • 1 行目には、生徒の数 N、友人関係の数 M、初めに噂を知っている生徒の数 K、噂が伝わるために必要な友人の人数の閾値 T が、スペース区切りで与えられる。
  • 2 行目には、初めに噂を知っている生徒の番号 C_1, C_2, \ldots, C_K がスペース区切りで与えられる。
  • 3 行目から M + 2 行目には、友人関係が M 行で与えられる。
  • 2 + i 行目 (1 \leq i \leq M) には、i 番目の友人関係における生徒の番号 u_i と v_i がスペース区切りで与えられる。

出力

噂の拡散が収束した後に噂を知っている生徒の人数を 1 行で出力せよ。

入力例 1

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

出力例 1

5

入力例 2

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

出力例 2

2

入力例 3

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

出力例 3

10

入力例 4

18 30 3 2
1 2 3
1 4
2 4
2 5
3 5
4 6
5 6
4 7
5 7
6 8
7 8
6 9
7 9
8 10
9 10
8 11
9 11
10 12
11 12
10 13
11 13
12 14
13 14
3 15
5 15
14 16
15 16
14 17
15 17
16 18
17 18

出力例 4

18

入力例 5

1 0 1 1
1

出力例 5

1

Score : 366 pts

Problem Statement

There are N students in Takahashi's school, numbered from 1 to N. M friendship relations between students are given, where the i-th friendship relation indicates that student u_i and student v_i are friends with each other (friendships are bidirectional). Note that the same friendship relation is never given more than once, and no student is friends with themselves.

Initially, only K students C_1, C_2, \ldots, C_K know a certain rumor. Starting from this initial state, the rumor spreads day by day according to the following rules:

> Evaluation: At the beginning of each day, for each student who does not yet know the rumor, count the number of their friends who currently know the rumor. If this number is at least T, that student will newly learn the rumor at the end of that day.

>

> Simultaneous Update: If multiple students newly learn the rumor on a given day, they all learn it simultaneously at the end of that day. Even if a student newly learns the rumor at the end of a day, this does not affect the evaluation of other students on the same day.

This process is repeated every day until no new students learn the rumor.

Determine the number of students who know the rumor in the end.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq K \leq N
  • 1 \leq T \leq N
  • 1 \leq C_i \leq N (1 \leq i \leq K)
  • All C_i are distinct
  • 1 \leq u_i < v_i \leq N (1 \leq i \leq M)
  • All pairs (u_i, v_i) are distinct
  • All input values are integers

Input

N M K T
C_1 C_2 \ldots C_K
u_1 v_1
u_2 v_2
\vdots
u_M v_M
  • The first line contains the number of students N, the number of friendships M, the number of students who initially know the rumor K, and the threshold number of friends required for the rumor to spread T, separated by spaces.
  • The second line contains the student numbers C_1, C_2, \ldots, C_K of those who initially know the rumor, separated by spaces.
  • From the 3rd line to the (M + 2)-th line, M friendship relations are given.
  • The (2 + i)-th line (1 \leq i \leq M) contains the student numbers u_i and v_i of the i-th friendship relation, separated by spaces.

Output

Print the number of students who know the rumor after the spread has converged, in a single line.

Sample Input 1

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

Sample Output 1

5

Sample Input 2

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

Sample Output 2

2

Sample Input 3

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

Sample Output 3

10

Sample Input 4

18 30 3 2
1 2 3
1 4
2 4
2 5
3 5
4 6
5 6
4 7
5 7
6 8
7 8
6 9
7 9
8 10
9 10
8 11
9 11
10 12
11 12
10 13
11 13
12 14
13 14
3 15
5 15
14 16
15 16
14 17
15 17
16 18
17 18

Sample Output 4

18

Sample Input 5

1 0 1 1
1

Sample Output 5

1