CF455C.Civilization

Andrew plays a game called "Civilization". Dima helps him.

The game has n cities and m bidirectional roads. The cities are numbered from 1 to n. Between any pair of cities there either is a single (unique) path, or there is no path at all. A path is such a sequence of distinct cities _v_1, _v_2, ..., v__k, that there is a road between any contiguous cities v__i and v__i + 1 (1 ≤ i < k). The length of the described path equals to (k - 1). We assume that two cities lie in the same region if and only if, there is a path connecting these two cities.

During the game events of two types take place:

1. Andrew asks Dima about the length of the longest path in the region where city x lies.
2. Andrew asks Dima to merge the region where city x lies with the region where city y lies. If the cities lie in the same region, then no merging is needed. Otherwise, you need to merge the regions as follows: choose a city from the first region, a city from the second region and connect them by a road so as to minimize the length of the longest path in the resulting region. If there are multiple ways to do so, you are allowed to choose any of them.

Dima finds it hard to execute Andrew's queries, so he asks you to help him. Help Dima.

安德鲁玩一款名为“文明”的游戏，迪马协助他。

游戏中有 $n$ 座城市和 $m$ 条双向道路。城市编号为 $1$ 到 $n$。任意两座城市之间，要么存在唯一的一条路径，要么根本不存在路径。一条路径是指一个由互不相同的城市组成的序列 $v_1,\,v_2,\,\dots,\,v_k$，使得对任意相邻的城市 $v_i$ 与 $v_{i+1}$（其中 $1 \le i < k$），均存在一条连接它们的道路。上述路径的长度定义为 $k - 1$。我们规定：当且仅当两座城市之间存在路径时，它们属于同一区域。

游戏过程中会发生两类事件：

1. 安德鲁向迪马询问：城市 $x$ 所在区域中最长路径的长度是多少？
2. 安德鲁要求迪马将城市 $x$ 所在区域与城市 $y$ 所在区域合并。若两座城市已在同一区域，则无需操作；否则需按如下方式合并两个区域：从第一个区域中选一座城市，从第二个区域中选一座城市，并用一条道路将它们连接起来，使得合并后新区域中最长路径的长度尽可能小。若存在多种方案均可达到该最小值，则任选其一即可。

迪马难以高效处理安德鲁的查询，因此请求你的帮助。请帮助迪马。

The first line contains three integers n, m, q (1 ≤ n ≤ 3·105; 0 ≤ m < n; 1 ≤ q ≤ 3·105) — the number of cities, the number of the roads we already have and the number of queries, correspondingly.

Each of the following m lines contains two integers, a__i and b__i (a__i ≠ b__i; 1 ≤ a__i, b__i ≤ n). These numbers represent the road between cities a__i and b__i. There can be at most one road between two cities.

Each of the following q lines contains one of the two events in the following format:

• 1 x__i. It is the request Andrew gives to Dima to find the length of the maximum path in the region that contains city x__i (1 ≤ x__i ≤ n).
• 2 x__i y__i. It is the request Andrew gives to Dima to merge the region that contains city x__i and the region that contains city y__i (1 ≤ x__i, y__i ≤ n). Note, that x__i can be equal to y__i.

第一行包含三个整数 $n$、$m$、$q$（$1 ≤ n ≤ 3·10^5$；$0 ≤ m < n$；$1 ≤ q ≤ 3·10^5$），分别表示城市的数量、已有的道路数量以及查询的数量。

接下来的 $m$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$a_i ≠ b_i$；$1 ≤ a_i, b_i ≤ n$），表示城市 $a_i$ 与城市 $b_i$ 之间的一条道路。任意两座城市之间至多只有一条道路。

接下来的 $q$ 行，每行描述以下两种事件之一，格式如下：

• 1 x_i：这是 Andrew 向 Dima 提出的请求，要求找出包含城市 $x_i$ 的连通区域中最长路径的长度（$1 ≤ x_i ≤ n$）。
• 2 x_i y_i：这是 Andrew 向 Dima 提出的请求，要求将包含城市 $x_i$ 的连通区域与包含城市 $y_i$ 的连通区域合并（$1 ≤ x_i, y_i ≤ n$）。注意，$x_i$ 可能等于 $y_i$。

For each event of the first type print the answer on a separate line.

对于每种第一类事件，在单独的一行上输出答案。