33OJ
登录 注册

#P17804. [ICPC 2019 Nanchang R] 9102

[ICPC 2019 Nanchang R] 9102

Problem Description

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 nn tribes on Mars and at the beginning, each tribe consists of the unique family. We number these tribes as well as these families from 11 to nn. Your program needs to support the following five types of operations:

  • 1 k a b: merge the tribe containing the aa-th family and the tribe containing the bb-th family;
  • 2 k a: make the aa-th family into extermination;
  • 3 k a b: the aa-th family moves away from their tribe and join in the tribe containing the bb-th family;
  • 4 k a b: report that if the aa-th family and the bb-th one belong to the same tribe;
  • 5 k a: report the total number of families in the tribe which contains the aa-th family.

Note that for each given operation with a parameter kk, you will place yourself in the world line at the time after the kk-th operation.

It is possible that the aa-th family and the bb-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 aa or bb 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.

Input Format

The first line contains two numbers nn and mm (1≤n,m≤10000001 \leq n, m \leq 1000000), representing the initial number of families and operations.

The next mm lines contain five kinds of operations. The ii-th line contains three or four numbers opiop_i, kik_i, aia_i and bib_i ($1 \leq op_i \leq 5, 0 \leq k_i \leq i-1, 1 \leq a_i, b_i \leq n$).

Output Format

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.

4 6 
1 0 1 2 
1 0 4 2 
3 2 4 3 
5 3 3 
2 1 1 
4 5 3 4
2
No

Hint

:::align{center} :::