P5064 [Ynoi Easy Round 2014] 等这场战争结束之后
题目背景
我真的能变强吗?

【就算你不愿意,我也会逼你变强】
那么承蒙你的一片美意,我就直说了吧

那个嘛...
我才不想变强呢~!
【那这样吧,只要你从战场上活着回来】
【我可以答应你随便一个要求,随便什么都行】
诶?

【结婚什么的当然免谈啦】
你说什么都行的...

点心...
你之前不是在食堂做了点心吗
那么黄油蛋糕你会做吗

我的姐姐...也就是前辈们当中
有一个人每次从战场上活着回来之后
都会一脸陶醉地品尝黄油蛋糕
所以...拜托你了
【偏偏挑这个...】
【没问题,我会让你吃到吐的】
【所以,你一定要活着回来】
题目描述
给你一个图,每个点有点权,最开始没有边。
有一些操作:
1. 添加一条 $x$ 与 $y$ 之间的双向边。
2. 回到第 $x$ 次操作后的状态(注意这里的 $x$ 可以是 $0$,即回到初始状态)。
3. 查询 $x$ 所在联通块能到的点中点权第 $y$ 小的值,如果不存在,那么输出 $-1$。
输入格式
无
输出格式
无
说明/提示
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 )
对于 $100\%$ 的数据,$1\leq n,m\leq 10^5$,$0\leq a_i\leq 10^9$。