CHM#1884
Your task is to implement a Persistent Disjoint-Set-Union. What does this mean?
About Disjoint-Set-Union:
Initially, you have elements. You need to be able to respond to types of queries:
— unite the sets containing elements and ;
— determine whether elements and are currently in the same set.
About Persistent:
Now, there will be several versions of the Disjoint-Set-Union data structure.
Queries will look like this:
— this is a query to the -th version; unite the sets containing and . The -th version remains unchanged; a new version is created, which receives a new version number (which? See below);
— this is a query to the -th version; determine whether and are currently in the same set in that version.
The first line contains two integers (1 \leq N \leq 10^5) and (0 \leq K \leq 10^5) — the number of elements and the number of queries. Initially, all elements are in different sets. This initial version of the structure has number .
Then follow lines, each containing the description of a query as described above. Queries are numbered from to .
When processing the -th query of the form , the new version gets the number .
There will be no queries to non-existent versions (j > i).
For each query of the form , output YES or NO on a separate line.
Example 1