P2195 HXY造公园

题目描述

有 $n$ 个点和 $m$ 条双向边。两种操作：

1. 对某个点 $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)$，都有边相连接，那么 $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 询问的回答。

输入输出样例 #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\%$ 的数据，$0\le m<n\le 20$，$1\le q\le5$。
• 对于 $60\%$ 的数据，$0\le m<n \le 2000$，$1\le q\le 1000$。
• 对于 $100\%$ 的数据，$0 \le m<n \le 3\times 10^5$，$1\le q\le 3\times 10^5$。