Problem Statement

Implement a Union-Find data structure that supports two operations:

• UNION a b — merge the sets containing elements a and b
• FIND a — output the root representative of element a's set

Implementation requirements:

• Union by rank: when merging, attach the lower-rank tree under the higher-rank tree.
• Tie-breaking: when ranks are equal, the element with the smaller index becomes the root.
• Path compression: use path halving (parent[x] = parent[parent[x]]) during find.

Function signature:

def union_find_sim(n: int, ops: list) -> list:
    # returns list of outputs for FIND queries (in order)

Input Format

Line 1: n q — number of elements (0 to n-1) and number of operations
Lines 2..q+1: one operation per line (UNION a b or FIND a)

Output Format

One integer per line for each FIND query — the root of that element's set

Example

Input:

5 6
UNION 1 0
UNION 2 0
FIND 0
FIND 1
FIND 2
UNION 4 3

Output:

0
0
0

Notes

• After UNION 1 0: ranks are equal, so the smaller index (0) becomes root. Parent[1] = 0.
• After UNION 2 0: 0 has rank 1 > rank of 2 (rank 0), so 0 remains root. Parent[2] = 0.
• All three FIND queries return 0 (the root).
• UNION 4 3 has no query output.