题目描述

小红有一个n 个点 m 条边的图，任意两个点要么不连通，要么有且仅有一条路径，这个图构成了一个森林。小红有q次询问，每次:

$1~p$，输出$p$所在的连通块任意两点的最大距离；

$2~x~y$，如果$x$和$y$不连通，将$x$和$y$所在的连通块连通，需要保证连通后这个连通块最长路径最小;如果已经连通，不做任何操作。

请你帮助小红解决这些问题。

输入描述

第一行三个整数$n,m,q$，表示点数，边数和询问数。

接下来$m$行，每行两个整数$u,v$，表示$u$ 和$v$之间有一条边，保证输入是一个森林。

接下来$q$行，如果第一个数是1，则后面一个数是$p$，表示询问$p$所在的连通块任意两点的最大距离;如果第一个数是 2，则后面两个数是$x,y$，表示将$x$和$y$所在的连通块连通，需要保证连通后这个连通块最长路径最小;如果已经连通，不做任何操作。 $1\le m<n\le 10^5$ $1\le q\le 10^5$

$1\le u,v,p,x,y\le n$

输出描述

对于每个第一类询问，输出一行一个整数，表示p 所在的连通块任意两点的最大距离。

样例

输入

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

输出

1
1
0
3