Versioned Disjoint Set Union with Rollback

You are given \(n\) sets. Initially, the \(i\)-th set contains only the element \(i\). There are \(m\) operations. Each operation is one of the following three types:

• 1 a b: Merge the sets that contain elements \(a\) and \(b\).
• 2 k: Rollback. Revert the state of the sets to the state immediately after the \(k\)-th operation. (All operations, including queries, are counted.)
• 3 a b: Query whether \(a\) and \(b\) belong to the same set. Output 1 if they are in the same set and 0 otherwise.

The input begins with two integers \(n\) and \(m\) on the first line. The following \(m\) lines each contain one operation in the formats described above. For each operation of type 3, output the result on a separate line.

Note: Every operation (including queries) is counted towards the operation index. The rollback operation will restore the DSU to the state that existed immediately after the given operation.

inputFormat

The first line contains two integers \(n\) and \(m\) where \(1 \leq n, m \leq 10^5\) (constraints may vary).

Each of the next \(m\) lines contains an operation in one of the following formats:

• 1 a b — merge the sets containing \(a\) and \(b\).
• 2 k — rollback to the state after the \(k\)-th operation.
• 3 a b — query if \(a\) and \(b\) are in the same set.

outputFormat

For each operation of type 3, output one line containing 1 if the elements are in the same set or 0 otherwise.

sample

3 6
1 1 2
3 1 2
1 2 3
3 1 3
2 1
3 1 3

1
1
0