分数: 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