P3402 [Template] Persistent DSU (Union-Find)

Given $n$ sets, the $i$-th set initially contains only the element $i$. There are $m$ operations, of three types: - `1 a b` Merge the sets containing $a$ and $b$; - `2 k` Revert to the state right after the $k$-th operation (any of the three types counts as one operation). It is guaranteed that at least $k$ operations have already been performed (not counting this one). In particular, if $k=0$, revert to the initial state; - `3 a b` Query whether $a$ and $b$ belong to the same set; if yes, output $1$, otherwise output $0$.

The first line contains two integers $n$ and $m$. Then follow $m$ lines. On each line, first read an integer $opt$. If $opt=2$ then read an integer $k$; otherwise read two integers $a, b$, describing one operation.

For each operation of type $3$, output one line with one integer indicating the answer.

For $100\%$ of the testdata, $1 \le n \le 10^5$, $1 \le m \le 2 \times 10^5$, $1 \le a, b \le n$. Translated by ChatGPT 5