题目内容

在一个无向通信网络中，有 $n$ 个站点，编号为 $1 \sim n$，以及 $m$ 条光缆，编号为 $1 \sim m$。初始时所有光缆均正常运作。

定义每个站点的“重要性评分”为：该站点当前连接的光缆数量（即其在当前图中的度数）加上其站点编号。

网络维护员会依次进行 $q$ 次操作，操作类型如下：

• 操作 $1$：输入一个整数 $x$，表示拆除编号为 $x$ 的光缆。保证该光缆在拆除前未被拆除。
• 操作 $2$：输入一个整数 $u$，查询站点 $u$ 当前所在的连通子网中，所有站点的重要性评分的最大值。

请对于每个操作 $2$，输出对应的最大值。

数据范围与约束：站点数 $n$ 与操作次数 $q$ 均不超过 $2 imes 10^5$；光缆数量 $m$ 满足 $0 \le m \le \min(\frac{n(n-1)}{2}, 2 imes 10^5)$。图中不存在重边和自环，且操作 $1$ 给出的光缆编号一定合法。

输入描述

第一行输入三个正整数 $n, m, q$，分别表示站点数量、光缆数量、操作数量。 接下来 $m$ 行，第 $i$ 行输入两个整数 $u_i, v_i$，表示第 $i$ 条光缆连接的两个站点编号。 接下来 $q$ 行，每行先输入一个整数 $op$，表示操作类型（$1$ 或 $2$），随后输入一个整数 $x$：若 $op=1$，$x$ 表示被拆除的光缆编号；若 $op=2$，$x$ 表示被查询的站点编号。

输出描述

对于每个操作 $2$，输出一行一个整数，表示该次查询的结果。多个输出按操作顺序排列。

样例1

输入

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

输出

5
4
3

说明

初始时，所有 3 条光缆均存在，各站点度数分别为：1 号连 2 和 3（度 2），2 号连 1 和 3（度 2），3 号连 1 和 2（度 2）。重要性评分 = 编号 + 度数：$1+2=3$，$2+2=4$，$3+2=5$。整个图连通，最大值为 5。第 1 次操作查询 1 号站点，输出 5。

第 2 次操作拆除光缆 3（连接 1-3）。剩余边 1-2 和 2-3，形成链 1-2-3。度数变为：1 度 1，2 度 2，3 度 1。评分：$1+1=2$，$2+2=4$，$3+1=4$。第 3 次查询 1 所在连通块（全图仍连通），最大值为 4，输出 4。

第 4 次拆除光缆 2（连接 2-3），只剩边 1-2。1 度 1，2 度 1。评分 $1+1=2$，$2+1=3$。第 5 次查询 2，连通块为 {1,2}，最大值 3，输出 3。

样例2

输入

2 0 2
2 1
2 2

输出

1
2

说明

网络中没有光缆（$m=0$）。所有站点度数为 0。站点 1 的重要性评分为 $1+0=1$，站点 2 为 $2+0=2$。分别查询，输出 1 和 2。这是一个边界情况。

样例3

输入

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

输出

6
6
6

说明

4 个站点通过 4 条边形成环：1-2-3-4-1。每个站点度数均为 2。重要性评分：$1+2=3$，$2+2=4$，$3+2=5$，$4+2=6$。没有删除操作，全图始终连通。查询任意站点所在连通块，最大值均为 6。

样例4

输入

1 0 1
2 1

输出

1

说明

仅有一个站点 1，没有光缆。其度数恒为 0，重要性评分 $1+0=1$。查询结果 1。