CHM
Your task - to implement Persistent Disjoint-Set-Union. What does this mean?
About Disjoint-Set-Union:
Initially, you have n elements. We must learn to respond to two types of queries.
+ a b — combine a set that contains the vertices a and b;
say, are whether the top a and b now in one set.
About Persistent:
Now we will have multiple copies (versions) of the data structure Disjoint-Set-Union.
Requests will look like this:
+ i a b — a request to the i-th structure, to combine a set that contains the vertices a and b. In this case, the i-th structure remains unchanged, a new version, it is assigned a new number (which? Read on);
? i a b — a request to the i-th structure, say there are vertices a and b are in one set.
Input
On the first line 2 of the N (1 ≤ N ≤ 10^5) и K (0 ≤ K ≤ 10^5) — the number of items and the number of requests. Initially, all elements are in different sets. This is the original copy (version) of the structure is numbered 0.
Followed by K lines for each description of the next request. The format of queries described above. Requests are numbered from 1 to K.
In processing the j-th query of the form + i a b, the new version will get the number j.
Requests to non-existent version will not be (j > i).
Output
For each query type ? i a b on a separate line to display YES or NO.