← 返回题目列表

AtCoder · awc0100_g

G. 朋友圈

中文机器翻译题面 查看原题

分数: 366 分

问题陈述

有 N 高桥班的学生。学生的出勤号码是从 1 to N.

在这个班上,一些学生是彼此的朋友。有 M 友谊关系,以及 j第一个友谊是学生之间 U_j 和学生 V_j。友谊是双向的,通过友谊直接或间接联系的学生被认为属于同一群体。

有一天,老师联系特定的学生,向班级传达公告。收到联系的学生与同一组中的每个人分享该公告。

老师做了 Q 联系人,并在 k第次联系,老师联系了学生 S_k.

Takahashi 想知道有多少学生实际收到了每次联系的通知。对于每个联系人,查找收到通知的学生总数。

约束

  • 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,那么 (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
  • 第一行包含 N,学生人数,以及 M,好友数量,以空格分隔。
  • 从第 2 行到 (M + 1)第行,给出友情信息。
  • 的 (1 + j)- 第行包含出勤人数 U_j 和 V_j 通过以下方式连接的学生 j第-个友谊,以空格分隔。
  • 的 (M + 2)- 第行包含 Q,联系人数量。
  • 从 (M + 3)第 行 (M + 2 + Q)第行,给出了老师联系的学生的考勤号码。
  • 的 (M + 2 + k)第行包含考勤号码 老师联系的学生的 S_k 老师联系过的学生的 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