Overview

This is a problem about managing student groupings, where we need to efficiently perform group merging and size retrieval.

Analysis

In this problem, we can consider a graph where students are vertices and groups are connected components. Instruction 1 (merging groups) corresponds to combining two connected components into one on the graph, and Instruction 2 (getting group size) corresponds to finding the number of vertices in the connected component containing a given vertex.

A naive approach would be to manage groups using lists or sets and move all members during each merge, but in the worst case, a single operation takes \(O(N)\), resulting in \(O(QN)\) overall, which is too slow (TLE).

Therefore, we use a data structure called Union-Find tree (or Disjoint Set Union) that can efficiently perform group merging and size retrieval. In a Union-Find tree, each element has a tree structure with a parent pointer, and groups are managed using the root as the representative. Furthermore, by applying path compression and merge optimization by rank/size, operations can be performed in nearly constant time.

Additionally, since printing the output of Instruction 2 one by one may be slow, the results are first stored in a list and then output all at once at the end.

Algorithm

We use a Union-Find tree (Disjoint Set Union).

• Each student corresponds to a node, and initially every node is its own parent (i.e., each group contains only one person).
• unite(a, b): Merges the groups to which students \(a\) and \(b\) belong.
  • Find the root (representative) of each node using find, and merge only if they are different.
  • Attach the smaller tree to the larger one (union by size) to keep the tree height low.
• get_size(x): Returns the size of the group to which student \(x\) belongs.
  • Compress the path to the root (via find) and return the size stored at the root.

This algorithm allows group merging and size retrieval to be performed very efficiently.

Complexity

• Time complexity: \(O(N + Q \cdot \alpha(N))\) (\(\alpha(N)\) is the inverse Ackermann function, which can be considered effectively constant)
• Space complexity: \(O(N)\)

Implementation Notes

• Student numbers are 1-indexed, so they are converted to 0-indexed internally (by subtracting 1).
• sys.stdin.read is used for fast input processing to avoid TLE.
• Output is done all at once at the end using print('\n'.join(results)) for speedup.
• During unite, sizes are compared and the smaller tree is attached to the larger one for efficiency.

## Source Code

```python
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def unite(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return
        if self.size[px] < self.size[py]:
            px, py = py, px
        self.parent[py] = px
        self.size[px] += self.size[py]

    def get_size(self, x):
        return self.size[self.find(x)]

import sys
input = sys.stdin.read

def main():
    data = input().split()
    idx = 0
    N = int(data[idx]); idx += 1
    Q = int(data[idx]); idx += 1

    uf = UnionFind(N)

    results = []
    for _ in range(Q):
        t = int(data[idx]); idx += 1
        if t == 1:
            a = int(data[idx]) - 1; idx += 1
            b = int(data[idx]) - 1; idx += 1
            uf.unite(a, b)
        else:
            x = int(data[idx]) - 1; idx += 1
            results.append(str(uf.get_size(x)))

    print('\n'.join(results))

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.