#P7229. [2023省队模拟]上学
[2023省队模拟]上学
题目描述
给定一个有 个顶点的图,每个顶点有一个点权,初始没有边。共有 次操作。第 次操作可能是以下三种之一。
1 x y:添加一条连接 与 的双向边,允许 。2 x:回到第 次操作完成后的状态。保证 。 表示回到初始状态。3 x y:查询 所在连通块中第 小的点权。如果不存在,输出 。
输入格式
第一行两个整数 ,分别表示顶点数和操作数。第二行 个整数,依次表示各个顶点的点权。
接下来 行,每行一个上述操作。
输出格式
对于每次类型为 的操作,输出一行一个整数表示答案。
样例输入
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
数据范围与约定
对于所有数据,,输入的所有数在 int 范围内。
- 子任务 1(20 分):。
- 子任务 2(20 分):不存在类型为 的操作。
- 子任务 3(60 分):空间小于 得本子任务 的分数,空间小于 得本子任务 的分数。