Description

You are given a graph. Each vertex has a weight, and initially there are no edges.

There are some operations:

1. Add an undirected edge between $x$ and $y$.
2. Revert to the state after the $x$-th operation (note that $x$ can be $0$, which means reverting to the initial state).
3. Query the $y$-th smallest vertex weight among the vertices reachable in the connected component containing $x$. If it does not exist, output $-1$.

Input Format

The first line contains two integers $n,m$, meaning there are $n$ vertices and $m$ operations.

The next line contains $n$ numbers, giving the weight of each vertex.

Then follow $m$ lines, each being one of the following three types:

1 x y

2 x

3 x y

Their meanings are as described in the statement.

Output Format

For every operation of type $3$, output one line containing one integer, which is the answer.

6 10
816801151 223885531 110182151 94271893 319888699 106363731 
1 1 3
1 3 5
1 2 4
1 4 6
1 1 2
3 1 1
2 4
1 1 2
3 1 4
2 7

94271893
223885531

Hint

Idea: nzhtl1477.

Solution: nzhtl1477( $O( nm/w )$ Time , $O( n\log n )$ Space )，ccz181078( $O( m\sqrt{n\log n} )$ Time ，$O(n\sqrt{n\log n} )$ Space ) ，shadowice1984( $O( m\sqrt{n\log n} )$ Time , $O( n\log n )$ Space ) , zx2003( $O( m\sqrt{n} )$ Time ，$O( n )$ Space ).

Code: nzhtl1477( $O( nm/w )$ Time , $O( n\log n )$ Space )，ccz181078( $O( m\sqrt{n\log n} )$ Time , $O( n\sqrt{n\log n} )$ Space ) ，shadowice1984( $O( m\sqrt{n\log n} )$ Time ，$O( n\log n )$ Space )，zx2003( $O( m\sqrt{n} )$ Time ，$O( n )$ Space ).

Data: nzhtl1477( partially uploaded ).

Constraints: for $100\%$ of the testdata, $1\leq n,m\leq 10^5$ and $0\leq a_i\leq 10^9$.

Translated by ChatGPT 5