← 返回题目列表

Codeforces · 1423/H

H. 病毒

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

在 Bubbleland 中,一群特殊编程部队获得了一项绝密工作,以计算一种新的未知病毒可能感染的人数。该州人口为 $$$n$$$ ,每天都会有关于人与人之间新接触的新信息。特殊编程力量的工作是计算某个人在过去 $$$k$$$ 天内有多少联系人。

新病毒的潜伏期为 $$$k$$$ 天,在此之后人们认为不具有传染性。由于这种新病毒极其危险,政府将过去 $$$k$$$ 天内直接或间接接触过的每个人都标记为可疑,无论接触顺序如何。

这种病毒很奇怪,人们无法获得持久的免疫力。

您需要帮助特殊编程力量计算给定人员的可疑人数(与给定人员接触过的人数)。

开头 $$$n$$$ 有 3 个给定输入,其中 $$$n$$$ 是人口,$$$q$$$ 查询数量,$$$k$$$ 病毒潜伏时间(以天为单位)。每个查询都是以下三种类型之一:

1. ($$$x$$$, $$$y$$$) 人 $$$x$$$ 和人 $$$y$$$ 于当天相遇 ($$$x \neq y$$$)。
2. ($$$z$$$) 返回与$$$z$$$接触的人数,算上他自己。
3. 当日结束时移至第二天。

输入

输入的第一行包含三个整数 $$$n$$$ ($$$1 \le n\le 10^5$$$) 该州的人数、$$$q$$$ ($$$1 \le q\le 5×10^5$$$) 查询数量和 $$$k$$$ ($$$1 \le k\le 10^5$$$) 病毒潜伏时间天。

接下来的 $$$q$$$ 行均以整数 $$$t$$$ ($$$1 \le t\le 3$$$) 开头,表示查询的类型。

第一种类型 ($$$x \neq y$$$) 的查询中跟随一对整数 $$$x$$$ 和 $$$y$$$ ($$$1 \le x, y \le n$$$)。

第二种类型的查询中跟随一个整数$$$i$$$ ($$$1 \le i\le n$$$)。

第三类查询没有以下号码。

输出

对于第二种类型的查询,在单独的行上打印当前与给定人员联系的人数。

示例

输入 #1

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

输出 #1

4
1
1
3
1

输入 #2

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

输出 #2

4
1
4
4
3

输入 #3

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

输出 #3

1
1
5
2
1
1

注意

注意$$$1$$$和$$$2$$$第一天和第二天$$$1$$$和$$$3$$$是否有联系,$$$k$$$>$$$1$$$$$$3$$$的联系人数为$$$3$$$(人:1,2,3)。