Information Graph

题意翻译

# 题目描述： 在某公司中有n名员工（编号为1至n），开始时员工之间没有任何关系，在接下来的m天会发生以下事： 1.y成为了x的上司（x在那之前不会有上司） 2.员工x得到了一份文件，然后x把文件传给了他的上司，然后上司又传给了他的上司，以此类推，直到某人没有上司，将文件销毁 3.询问x是否看过某份文件。 # 输入格式: 第一行输入两个整数n，m（1<=n,m<=1e5）n,m含义见题目描述。接下来m行每行描述了一种操作，先读入事件的类型t， 1. 如果t=1，然后读入两个整数x,y（1<=x,y<=n）表示员工编号，y成为了x的上司，保证这时x不会有上司。 2. 如果t=2，然后读入一个整数x（1<=x<=n）表示编号为x的员工得到了一份文件（文件编号为上一份文件编号+1，第一份文件编号为1），具体操作见题目描述2。 3. 如果t=3，然后读入两个整数x，i，表示查询员工x是否阅读过文件i，保证i已经被输入。(就是不会出现这份文件还没被任何人读过的情况)。 保证输入至少有一个第三种类型的操作。 # 输出格式： 对于每一个操作3，如果这个员工阅读过这份文件则输出“YES”（不加引号），否则输出“NO”（不加引号）。（注意换行）。

题目描述

There are $ n $ employees working in company "X" (let's number them from 1 to $ n $ for convenience). Initially the employees didn't have any relationships among each other. On each of $ m $ next days one of the following events took place: - either employee $ y $ became the boss of employee $ x $ (at that, employee $ x $ didn't have a boss before); - or employee $ x $ gets a packet of documents and signs them; then he gives the packet to his boss. The boss signs the documents and gives them to his boss and so on (the last person to sign the documents sends them to the archive); - or comes a request of type "determine whether employee $ x $ signs certain documents". Your task is to write a program that will, given the events, answer the queries of the described type. At that, it is guaranteed that throughout the whole working time the company didn't have cyclic dependencies.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 1<=n,m<=10^{5} $ ) — the number of employees and the number of events. Each of the next $ m $ lines contains the description of one event (the events are given in the chronological order). The first number of the line determines the type of event $ t $ $ (1<=t<=3) $ . - If $ t=1 $ , then next follow two integers $ x $ and $ y $ $ (1<=x,y<=n) $ — numbers of the company employees. It is guaranteed that employee $ x $ doesn't have the boss currently. - If $ t=2 $ , then next follow integer $ x $ $ (1<=x<=n) $ — the number of the employee who got a document packet. - If $ t=3 $ , then next follow two integers $ x $ and $ i $ $ (1<=x<=n; 1<=i<= $ \[number of packets that have already been given\] $ ) $ — the employee and the number of the document packet for which you need to find out information. The document packets are numbered started from 1 in the chronological order. It is guaranteed that the input has at least one query of the third type.

输出格式

For each query of the third type print "YES" if the employee signed the document package and "NO" otherwise. Print all the words without the quotes.

输入输出样例

输入样例 #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