← 返回题目列表

Codeforces · 466/E

E. 信息图

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

公司“X”有n名员工(为了方便起见,我们将他们从1到n编号)。最初,员工之间没有任何关系。接下来的 m 天中,每一天都会发生以下事件之一:

- 员工 y 成为员工 x 的老板(此时员工 x 之前没有老板);
- 或员工 x 拿到一包文件并签名;然后他把包裹交给了他的老板。老板签署文件并交给他的老板等等(最后签署文件的人将文件发送到档案室);
- 或出现“确定员工 x 是否签署某些文档”类型的请求。

您的任务是编写一个程序,根据给定的事件,回答所描述类型的查询。这样就保证了公司在整个工作时间内不存在循环依赖。

输入

第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 105) — 员工数量和事件数量。

接下来的 m 行中的每一行都包含一个事件的描述(事件按时间顺序给出)。该行的第一个数字确定事件 t 的类型 (1 ≤ t ≤ 3)。

- 如果 t = 1,则接下来是两个整数 x 和 y (1 ≤ x, y ≤ n) — 公司员工人数。保证员工x当前没有老板。
- 如果 t = 2,则接下来是整数 x (1 ≤ x ≤ n) — 收到文档包的员工编号。
- 如果 t = 3,则接下来跟随两个整数 x 和 i (1 ≤ x ≤ n; 1 ≤ i ≤ [已给出的数据包数量]) — 员工和您需要查找信息的文档数据包的数量。文档包按时间顺序从 1 开始编号。

保证输入至少有一个第三类型的查询。

输出

对于第三种类型的每个查询,如果员工签署了文档包,则打印“是”,否则打印“否”。打印所有不带引号的单词。

示例

输入 #1

4 9
1 4 3
2 4
3 3 1
1 2 3
2 2
3 1 2
1 3 1
2 2
3 1 3

输出 #1

YES
NO
YES