Tree Operations using Union-Find

You are given n nodes numbered from 1 to n, initially having no connections between them.

You will be asked to perform q operations. There are two types of operations:

• 1 x y: Connect the nodes x and y, effectively merging their respective sets.
• 2: Query and report the current number of connected components.

Implement the above operations using the Union-Find (Disjoint Set Union) data structure with path compression and union by rank to ensure efficiency. The number of connected components should be updated after each union operation. Use the accurate latex formatted notation for any formulas, e.g., \(n\) for the number of nodes.

inputFormat

The first line contains two integers (n) and (q) ((1 \le n, q \le 10^5)), representing the number of nodes and the number of operations respectively. Each of the following (q) lines represents an operation. An operation of the form 1 x y indicates that you should union the sets containing nodes x and y. An operation of the form 2 requires you to output the current number of connected components.

outputFormat

For each operation of type 2, output the current number of connected components on a new line.## sample

5 5
1 1 2
2
1 2 3
2
1 4 5

4
3