G - Circle of Friends Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君のクラスには N 人の生徒がいます。生徒には 1 から N までの出席番号が付けられています。

このクラスでは、何人かの生徒同士が友達関係にあります。友達関係は M 組存在し、 j 番目の友達関係は生徒 U_j と生徒 V_j の間にあります。友達関係は双方向であり、また友達関係で直接または間接的に繋がっている生徒同士は同じグループに属しているとみなされます。

ある日、先生はクラスで連絡事項を伝えるために、特定の生徒に連絡をしました。連絡を受けた生徒は、同じグループに属する全員にその連絡を共有します。

先生は Q 回の連絡を行い、 k 回目の連絡では生徒 S_k に連絡をしました。

高橋君は、各連絡において実際に何人の生徒が連絡を受け取ったかを知りたいと思っています。各連絡について、連絡を受け取った生徒の総数を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq U_j < V_j \leq N (1 \leq j \leq M)
  • i \neq j ならば (U_i, V_i) \neq (U_j, V_j)
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq S_k \leq N (1 \leq k \leq Q)
  • 入力はすべて整数

入力

N M
U_1 V_1
U_2 V_2
:
U_M V_M
Q
S_1
S_2
:
S_Q
  • 1 行目には、生徒の数を表す N 、友達関係の数を表す M が、スペース区切りで与えられる。
  • 2 行目から M + 1 行目には、友達関係の情報が与えられる。
  • 1 + j 行目では、 j 番目の友達関係で結ばれている生徒の出席番号 U_j と V_j がスペース区切りで与えられる。
  • M + 2 行目には、連絡の回数を表す Q が与えられる。
  • M + 3 行目から M + 2 + Q 行目には、各連絡で先生が連絡した生徒の出席番号が与えられる。
  • M + 2 + k 行目では、 k 回目の連絡で先生が連絡した生徒の出席番号 S_k が与えられる。

出力

Q 行出力せよ。 k 行目には、 k 回目の連絡において連絡を受け取った生徒の総数を出力せよ。

入力例 1

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

出力例 1

3
2
3

入力例 2

6 2
1 3
2 4
4
1
5
2
6

出力例 2

2
1
2
1

入力例 3

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

出力例 3

4
3
2
1
3

入力例 4

15 10
1 2
2 3
3 4
4 5
6 7
7 8
9 10
10 11
11 12
13 14
8
1
6
9
13
15
5
8
12

出力例 4

5
3
4
2
1
5
3
4

入力例 5

1 0
1
1

出力例 5

1

Score : 366 pts

Problem Statement

There are N students in Takahashi's class. The students are assigned attendance numbers from 1 to N.

In this class, some pairs of students are friends with each other. There are M friendship relations, and the j-th friendship is between student U_j and student V_j. Friendships are bidirectional, and students who are connected directly or indirectly through friendships are considered to belong to the same group.

One day, the teacher contacted specific students to convey announcements to the class. A student who receives the contact shares the announcement with everyone in the same group.

The teacher made Q contacts, and in the k-th contact, the teacher contacted student S_k.

Takahashi wants to know how many students actually received the announcement for each contact. For each contact, find the total number of students who received the announcement.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq U_j < V_j \leq N (1 \leq j \leq M)
  • If i \neq j, then (U_i, V_i) \neq (U_j, V_j)
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq S_k \leq N (1 \leq k \leq Q)
  • All inputs are integers

Input

N M
U_1 V_1
U_2 V_2
:
U_M V_M
Q
S_1
S_2
:
S_Q
  • The first line contains N, the number of students, and M, the number of friendships, separated by a space.
  • From the 2nd line to the (M + 1)-th line, friendship information is given.
  • The (1 + j)-th line contains the attendance numbers U_j and V_j of the students connected by the j-th friendship, separated by a space.
  • The (M + 2)-th line contains Q, the number of contacts.
  • From the (M + 3)-th line to the (M + 2 + Q)-th line, the attendance number of the student the teacher contacted is given.
  • The (M + 2 + k)-th line contains the attendance number S_k of the student the teacher contacted in the k-th contact.

Output

Output Q lines. On the k-th line, output the total number of students who received the announcement in the k-th contact.

Sample Input 1

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

Sample Output 1

3
2
3

Sample Input 2

6 2
1 3
2 4
4
1
5
2
6

Sample Output 2

2
1
2
1

Sample Input 3

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

Sample Output 3

4
3
2
1
3

Sample Input 4

15 10
1 2
2 3
3 4
4 5
6 7
7 8
9 10
10 11
11 12
13 14
8
1
6
9
13
15
5
8
12

Sample Output 4

5
3
4
2
1
5
3
4

Sample Input 5

1 0
1
1

Sample Output 5

1