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$。