题目描述

一座公园里共有 $n$ 个休息点和 $m$ 条连接两个休息点的双向步道。小琦是个追求极致的规划师，她准备施展魔法逐步改造公园，并随时掌握改造效果。她每次会进行下面两种操作之一：

1. 给定休息点 $x$，询问在公园中能与 $x$ 互相到达的那些休息点所组成的区域里，最长路径的长度。
2. 给定两个休息点 $x,y$：若它们已经能互相到达，则本次操作直接忽略；否则，她在 $x$ 可达的所有休息点与 $y$ 可达的所有休息点（含 $x,y$ 本身）中各挑一个，在二者之间修一条新步道。挑选方案必须让新区域内最长路径的长度尽量小。

小琦一共要进行 $q$ 次操作，请回答每次操作 1 的询问，或执行操作 2 的修建。

注：所有步道长度均为 $1$，保证任意时刻不存在环。最长路径定义为：对于点列 $v_1,v_2\cdots v_k$，若其中任意相邻两点 $v_i$ 与 $v_{i+1}\quad (1\le i\le k-1)$ 都有步道直接相连，则该区域的最长路径长度就是 $k-1$。

输入格式

• 第一行，三个正整数，分别为 $n,m,q$。
• 接下来的 $m$ 行，每行两个正整数 $x_i,y_i$，表示 $x_i$ 与 $y_i$ 之间有一条双向步道。
• 再接下来的 $q$ 行，每行描述一次操作。
  • 若该行第一个数为 $1$，则是操作 1，之后还有一个正整数 $x_i$，表示要询问的休息点。
  • 若该行第一个数为 $2$，则是操作 2，之后还有两个正整数 $x_i,y_i$，表示本次要操作的两个休息点。

输出格式

输出的行数等于操作 1 的次数。

每行输出对对应操作 1 询问的回答。

样例

6 0 6
2 1 2
2 3 4
2 5 6
2 3 2
2 5 3
1 1

4

提示

数据范围及约定

• 对于 $10\%$ 的数据，只存在操作 1。
• 对于 $30\%$ 的数据，$0\le m\lt n\le 20$，$1\le q\le5$。
• 对于 $60\%$ 的数据，$0\le m\lt n \le 2000$，$1\le q\le 1000$。
• 对于 $100\%$ 的数据，$0 \le m\lt n \le 3\times 10^5$，$1\le q\le 3\times 10^5$。