分数: 6 点
警告
2020 年 12 月 27 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。 考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。
问题陈述
您运行的社交网络服务由 N 用户。用户,编号 1 通过 N,可以与其他用户建立双向友谊。
现在有 M 服务中的友谊,编号 1 通过 M;友谊 i 是在用户之间 a_i 和用户 b_i.
您的任务是向服务添加新功能。
流程 Q 按给出的顺序进行查询。的 i-th 查询为您提供整数 T_i 和 x_i,其含义如下:
- If T_i = 1:向每个用户发送通知(不包括用户) x_i) 是用户的直接朋友 x_i。这些通知最初是未读的。
- If T_i = 2:打印发送给用户的未读通知的数量 x_i。然后,这些通知被标记为已读。
约束
- 输入中的所有值都是整数。
- 2 \le N \le 2 \times 10^5
- 1 \le M \le 2 \times 10^5
- 1 \le a_i \lt b_i \le N
- If i \neq j,那么 (a_i, b_i) \neq (a_j, b_j).
- 1 \le Q \le 2 \times 10^5
- T_i \in \{1, 2\}
- 1 \le x_i \le N
输入
输入由标准输入按以下格式给出:
N M a_1 b_1 \vdots a_M b_M Q T_1 x_1 \vdots T_Q x_Q
输出
对于每个查询 T_i = 2,在自己的行中打印响应。
示例输入 1
3 2 1 2 1 3 5 1 1 2 2 1 1 2 3 2 1
示例输出 1
1 2 0
在第一个查询中,通知会发送给 User 的直接好友 1 - 用户 2 和 3。现在,用户 1, 2, 3 有
分别是 0, 1, 1 未读通知。
在第二个查询中,我们打印发送给用户的未读通知的数量 2,即 1。现在,用户 1, 2,和 3 有
分别是 0, 0,和 1 未读通知。
在第三个查询中,通知将发送给 User 的直接好友 1 - 用户 2 和 3。现在,用户 1, 2, 3 有
分别是 0, 1, 2 未读通知。
在第四个查询中,我们打印发送给用户的未读通知的数量 3,即 2。现在,用户 1, 2, 3 有
分别是 0, 1, 0 未读通知。
在第五个查询中,我们打印发送给用户的未读通知的数量 1,即 0。现在,用户 1, 2, 3 有
分别是 0, 1, 0 未读通知。
示例输入 2
7 7 1 4 1 6 3 4 3 5 3 7 4 5 4 7 15 1 1 2 3 1 4 2 2 1 5 1 1 1 4 2 4 2 3 2 1 1 7 1 2 2 5 2 4 2 2
示例输出 2
0 0 3 3 2 2 1 0
示例输入 3
10 13 1 2 1 5 1 9 2 3 2 4 3 5 3 6 3 9 4 8 5 7 5 10 6 7 6 10 20 1 5 2 8 1 4 2 9 1 1 1 6 2 8 1 10 2 7 1 10 1 10 2 8 1 7 2 5 1 9 2 2 1 9 1 4 2 4 2 6
示例输出 3
0 0 1 2 0 5 2 0 4