P17804 [ICPC 2019 Nanchang R] 9102

As everyone knows, there are innumerable "world lines" representing different worlds. Every tiny change maybe creates a new world line. It is 9102 A.D. now and human beings have lived on Mars for thousands of years, forming a lot of tribes. Every tribe contains one or more families. Two tribes can go to integration, which all families in one tribe move to the other; One family may become extinct or migrate from their original tribe to another family's tribe. You are ruling the universe as Creator so that you know everything on Mars. Because of the reason that you usually forget things, you decide to write a program to manage these happening things. Suppose that there are $n$ tribes on Mars and at the beginning, each tribe consists of the unique family. We number these tribes as well as these families from $1$ to $n$. Your program needs to support the following five types of operations: - `1 k a b`: merge the tribe containing the $a$-th family and the tribe containing the $b$-th family; - `2 k a`: make the $a$-th family into extermination; - `3 k a b`: the $a$-th family moves away from their tribe and join in the tribe containing the $b$-th family; - `4 k a b`: report that if the $a$-th family and the $b$-th one belong to the same tribe; - `5 k a`: report the total number of families in the tribe which contains the $a$-th family. Note that for each given operation with a parameter $k$, you will place yourself in the world line at the time after the $k$-th operation. It is possible that the $a$-th family and the $b$-th one are in the same tribe when you deal with an operation of type 1 or 3, then nothing will happen. It is also possible that given numbers $a$ or $b$ indicates to an exterminated family, then nothing will happen for the first three types of operations, and the report should be `No` for the fourth type of operation, and `0` for the fifth one.

The first line contains two numbers $n$ and $m$ ($1 \leq n, m \leq 1000000$), representing the initial number of families and operations. The next $m$ lines contain five kinds of operations. The $i$-th line contains three or four numbers $op_i$, $k_i$, $a_i$ and $b_i$ ($1 \leq op_i \leq 5, 0 \leq k_i \leq i-1, 1 \leq a_i, b_i \leq n$).

For operation 4, you need to output one line `Yes` or `No` (without quotes); for operation 5, you need to output one line contains a number.

:::align{center}  :::