题目内容

运营商维护一个由 n 个站点组成的通信网络，站点编号为 1 到 n。网络中存在 m 条双向光纤，光纤编号为 1 到 m。初始时，所有光纤均处于工作中。

定义每个站点的负载指数为其当前连接的纤数量（即度数）加上该站点的编号。

工程师将依次执行 q 次操作，操作分为两类：

• 操作一：拆除一条指定编号的光纤，该光纤必须存在且每一条只被拆除一次。
• 操作二：查询某个指定站点所在的连通子网中，所有站点的负载指数的最大值。

连通子网是指满足以下条件的极大子图：内部任意两站点之间存在路径相连；单独一个站点也视为一个连通子网。

约束：站点数量 n 与操作次数 q 均不超过 $2 imes 10^5$，光纤数量 m 不超过 $2 imes 10^5$。所有编号均在有效范围内，保证网络中没有重边和自环，拆除操作总是合法的。

输入描述

第一行包含三个正整数 n、m 和 q，分别表示站点数、光纤数和操作次数。 接下来 m 行，第 i 行包含两个整数 u_i 和 v_i，表示第 i 条光纤连接的两个站点。 接下来 q 行，每行描述一个操作。首先给出操作类型 o_i（1 或 2），若 o_i = 1 则后跟一个整数 x_i 表示被拆除的光纤编号，若 o_i = 2 则后跟一个整数 x_i 表示需要查询的站点编号。

输出描述

对于每个操作二，按操作出现的顺序，每行输出一个整数，表示对应查询中连通子网的最大负载指数。

样例1

输入

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

输出

4
1
4

说明

网络有 3 个站点和 2 条光纤：边 1 连接站点 1 与 2，边 2 连接站点 2 与 3。初始时全图连通。 各站点初始度数：站点 1 度数为 1，站点 2 度数为 2，站点 3 度数为 1。负载指数为编号加度数：站点 1 为 $1+1=2$，站点 2 为 $2+2=4$，站点 3 为 $3+1=4$。连通子网最大值为 $\max(2,4,4)=4$。 第一次操作查询站点 2，所在连通子网最大值仍为 4。 第二次操作拆除光纤 1（即 1-2），网络分裂为两个连通子网：{1} 和 {2,3}。拆除后站点 1 度数变为 0，负载指数变为 $1+0=1$；站点 2 度数变为 1，负载指数变为 $2+1=3$；站点 3 不变。 第三次操作查询站点 1，其所在子网 {1} 的最大值为 1。 第四次操作查询站点 2，其所在子网 {2,3} 的最大值为 $\max(3,4)=4$。

样例2

输入

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

输出

5
5
3
2

说明

网络有 4 个站点和 3 条光纤，形成链状结构 1-2-3-4。 初始度数：站点 1 度 1，站点 2 度 2，站点 3 度 2，站点 4 度 1。负载指数：站点 1 为 $1+1=2$，站点 2 为 $2+2=4$，站点 3 为 $3+2=5$，站点 4 为 $4+1=5$。全图连通，最大值为 5。 第一次操作查询站点 1，结果为 5。 第二次操作拆除光纤 2（即 2-3），图分裂为 {1,2} 与 {3,4}。此时度数更新：站点 2 变为 1，站点 3 变为 1。子网 {1,2} 内负载指数为站点 1 $1+1=2$、站点 2 $2+1=3$，最大值 3；子网 {3,4} 内站点 3 $3+1=4$、站点 4 $4+1=5$，最大值 5。 第三次操作查询站点 3，所在子网 {3,4} 最大值为 5。 第四次操作查询站点 1，所在子网 {1,2} 最大值为 3。 第五次操作拆除光纤 1（即 1-2），子网 {1,2} 进一步分裂为 {1} 和 {2}。度数变化后站点 1 度 0（指数 1），站点 2 度 0（指数 2）。 第六次操作查询站点 2，所在子网 {2} 最大值为 2。

样例3

输入

1 0 1
2 1

输出

1

说明

边界情形：只有一个站点 1 且无光纤。站点 1 的度数为 0，负载指数为 $1+0=1$。查询站点 1 所在连通子网的最大值，仅有一个站点，故结果为 1。