解题思路

这题正序是删边，并查集不好直接维护连通块分裂，所以要用逆序离线。

把所有操作倒过来以后：

• 删边变成加边
• 查询还是查询

题目内容

给你一个由 $n$ 个编号为 $1$ ~ $n$ 的节点以及 $m$ 条编号为 $1$ ~ $m$ 的边组成的无向图，我们定义一个节点的权值为它的当前 度$^{[1]}$(即已执行完之前所有操作后的状态)加上它的节点编号。

小美会进行 $q$ 次如下操作：

• 操作一：断开编号为 $x$ 的边，保证每条边至多被删除一次，即在进行操作一时，该边当前一定存在于图中。

• 操作二：向你询问编号为 $2$ 的节点所在的 连通块$^{[2]}$ 中所有节点中最大的权值，你需要将此权值告诉他。

【名词解释】

度$^{[1]}$：与一个顶点相连接的边的条数称为该顶点的度。

连通块$^{[2]}$ ：也称连通分量，满足，

• 是原图的一个子图;

• 连通块内的任意两个顶点之间都存在路径相连，且路径上的点也在连通块内;

• 是极大的，即不能再通过添加原图中的其他顶点而依旧保持连通性;

• 单独的点也构成一个连通块。连通块的大小即为连通块中顶点的数量。

输入描述

第一行输入三个正整数

$n,m,q(1≤n,q≤2×10^5;0≤m≤min${$\frac{n×(n-1)}{2},2×10^5$}$)$ 表示节点个数，边个数，操作次数。

此后 $m$ 行，第 $i$ 行输入两个整数 $u_i$ 和 $v_i(1≤u_i,v_i≤n;u_i≠v_i)$ 表示图上第 $i$ 条边连接节点 $u_i$ 和 $v_i$ 。

此后 $q$ 行，第 $i$ 行先输入一个整数 $o_i(1≤o_i≤2)$，表示操作编号。编号同题面，随后在同一行：

• 若 $o_i=1$，输入一个整数 $x_i(1≤x_i≤m)$，表示断掉的边的编号;

• 若 $o_i=2$，输入一个整数 $x_i(1≤x_i≤n)$，表示询问的节点编号。

保证图没有重边和自环，操作一合法。

输出描述

输出若干行，每一行对操作二进行回答。

样例1

输入

5 5 5
1 2
1 5
3 5
2 4
1 3
2 4
1 1
2 2
1 2
2 1

输出

7
5
6