Problem Statement

Implement a Union-Find (Disjoint Set Union) data structure that supports three operations:

• UNION a b — merge the sets containing a and b
• SAME a b — output 1 if a and b are in the same set, 0 otherwise
• SIZE a — output the size of the set containing a

Implementation requirements:

• Use union by rank with tie-breaking: when ranks are equal, the element with the smaller index becomes the root.
• Use path compression (path halving: parent[x] = parent[parent[x]]).
• Track set sizes for SIZE queries.

Function signature:

def disjoint_set_ops(n: int, ops: list) -> list:
    # returns list of outputs for SAME and SIZE 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, SAME a b, or SIZE a)

Output Format

One integer per line for each SAME or SIZE query (in order)

Example

Input:

5 7
UNION 0 1
UNION 1 2
SAME 0 2
SAME 0 3
SIZE 0
UNION 3 4
SIZE 3

Output:

1
0
3
2

Notes

• After UNION 0 1 and UNION 1 2, elements 0, 1, 2 are in the same set of size 3.
• Element 3 is in its own set, so SAME 0 3 = 0 and SIZE 0 = 3.
• After UNION 3 4, elements 3 and 4 form a set of size 2, so SIZE 3 = 2.