HXY造公园

题目描述

现在有一个现成的公园,有 $n$ 个休息点和 $m$ 条双向边连接两个休息点。众所周知,HXY 是一个 SXBK 的强迫症患者,所以她打算施展魔法来改造公园并即时了解改造情况。她可以进行以下两种操作: 1. 对某个休息点 $x$,查询公园中可以与该点互相到达的休息点组成的路径中的最长路径。 2. 对于两个休息点 $x,y$,如果 $x,y$ 已经可以互相到达则忽略此次操作。否则,在 $x$ 可到达的所有休息点和 $y$ 可到达的所有休息点(包括 $x,y$ 自身)分别选择一个休息点,然后在这两个休息点之间连一条边,并且这个选择应该满足对于连接后的公园,$x$ 和 $y$ 所在的区域(即 $x,y$ 可达到的所有休息点和边组成的集合)中的最长路径的长度最小。 HXY打算进行 $q$ 个操作,请你回答她的对于公园情况的询问(操作 1)或者执行她的操作(操作 2)。 注:所有边的长度皆为 $1$。保证不存在环。最长路径定义为:对于点 $v_1,v_2\cdots v_k$,如果对于其中任意的 $v_i$ 和 $v_{i+1}\quad (1\le i\le k-1)$,都有边相连接,那么 $v_j\quad(1\le j\le k)$ 所在区域的最长路径就是 $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 询问的回答。

输入输出样例

输入样例 #1

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

输出样例 #1

4

说明

### 数据范围及约定 - 对于 $10\%$ 的数据,只存在操作 1。 - 对于 $30\%$ 的数据,$1\le m<n\le 20$,$1\le q\le5$。 - 对于 $60\%$ 的数据,$1\le m<n \le 2000$,$1\le q\le 1000$。 - 对于 $100\%$ 的数据,$1 \le m<n \le 3\times 10^5$,$1\le q\le 3\times 10^5$。