← 返回题目列表

AtCoder · past202012_o

O. 通知

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

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