题目描述

现在有一个现成的公园，有n个休息点和m条双向边连接两个休息点。众所周知，HXY是一个SXBK的强迫症患者，所以她打算施展魔法来改造公园并即时了解改造情况。她可以进行以下两种操作：

1、对某个休息点x，查询公园中可以与个点互相到达的休息点组成的路径中的最长路径

2、对于两个休息点x、y，如果x，y已经可以互相到达则忽略此次操作。否则，在x可到达的所有休息点和y可到达的所有休息点（包括x，y自身）分别选择一个休息点，然后在这两个休息点之间连一条边，并且这个选择应该满足对于连接后的公园，x和y所在的区域（即x，y可达到的所有休息点和边组成的集合）中的最长路径的长度最小。

HXY打算进行q个操作，请你回答她的对于公园情况的询问（操作1）或者执行她的操作（操作2）。

注：所有边的长度皆为1。保证不存在环。最长路径定义为：对于点v1,v2......vk，如果对于其中任意的vi和vi+1(1<=i<=k-1)，都有边相连接，那么vj(1<=j<=k)所在区域的最长路径就是k-1。

输入格式

第一行，三个正整数，分别为n，m，q。

接下来的m行，每一行有两个正整数xi，yi，表示xi和yi有一条双向边相连。

再接下来的q行，每一行表示一个操作。

若该行第一个数为1，则表示操作1，之后还有一个正整数xi，表示要查询的休息点。

若该行第一个数为2，则表示操作2，之后还有两个正整数xi，yi，表示需要执行操作的两个休息点。

输出格式

输出行数为操作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%的数据，1<=m<n<=20,1<=q<=5。

对于60%的数据，1<=m<n<=2000,1<=q<=1000。

对于100%的数据，1<=m<n<=3*10^5,1<=q<=3*10^5。