You are given a graph consisting of N nodes. Initially, there is no edge in the graph. You have to process Q queries of the following two types:
Note that the edges connected in the type 2 query are not considered in further queries.
Note: Since the size of input-output is large, prefer using fast input-output methods.
Input format
Output format
For each query of type 2, print the size of the largest connected component in a separate line.
Constraints
2≤N,Q≤4⋅1051≤xi<yi≤N1≤typei≤21≤K≤N
Query 1: Add an edge between nodes 1 and 2 and another edge between nodes 1 and 3. Now the nodes 1, 2 and 3 form the largest component.
Query 2: Nodes 2 and 3 are connected with an edge.
Query 3: Add an edge between nodes 2 and 4. Now the nodes 2, 3 and 4 form the largest component.
Query 4: Nodes 1 and 5 are connected with an edge.
Query 5: Nodes 1 and 2 are connected with an edge.
Query 6: Add an edge between nodes 4 and 5. Now the nodes 1, 2, 3, 4 and 5 form the largest component.