Background

Can I really become stronger?

【Even if you don’t want to, I will force you to become stronger.】
Then, thanks for your kindness, I’ll say it directly.

Well...
I don’t want to become stronger at all~!
【Then how about this: as long as you come back alive from the battlefield.】
【I can promise you any one request, anything at all.】
Huh?

【Marriage is of course out of the question.】
You said anything...

Desserts...
Didn’t you make desserts in the cafeteria before?
Then, can you make butter cake?

My older sister... that is, among the seniors,
there is someone who, every time she comes back alive from the battlefield,
will taste butter cake with a blissful look on her face.
So... please.
【Of all things, you picked this...】
【No problem. I’ll make you eat until you throw up.】
【So, you must come back alive.】

Problem 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