← 返回题目列表

Codeforces · 455/C

C. 文明

中文机器翻译题面 查看原题

安德鲁玩一款名为“文明”的游戏。迪玛帮助他。

游戏有n个城市和m条双向道路。城市编号为 1 到 n。任何一对城市之间要么只有一条(唯一)路径,要么根本没有路径。路径是不同城市 v1, v2, ..., vk 的序列,任何相邻城市 vi 和 vi + 1 (1 ≤ i < k) 之间都有一条道路。所描述的路径的长度等于(k-1)。我们假设两个城市位于同一区域当且仅当有一条路径连接这两个城市。

游戏期间会发生两种类型的事件:

1. Andrew 向 Dima 询问城市 x 所在区域的最长路径的长度。
2. Andrew 要求 Dima 将城市 x 所在的区域与城市 y 所在的区域合并。如果城市位于同一区域,则无需合并。否则,您需要按如下方式合并区域:从第一个区域中选择一个城市,从第二个区域中选择一个城市,并通过道路将它们连接起来,以最小化结果区域中最长路径的长度。如果有多种方法可以实现,您可以选择其中任何一种。

Dima 发现很难执行 Andrew 的查询,因此他请你帮助他。帮助迪玛。

输入

第一行包含三个整数 n、m、q (1 ≤ n ≤ 3·105; 0 ≤ m < n; 1 ≤ q ≤ 3·105) — 相应的城市数量、已有道路数量和查询数量。

以下 m 行每行包含两个整数 ai 和 bi(ai ≠ bi;1 ≤ ai,bi ≤ n)。这些数字代表城市 ai 和 bi 之间的道路。两个城市之间最多只能有一条道路。

以下 q 行中的每一行均包含以下格式的两个事件之一:

- 1 xi。这是Andrew向Dima提出的要求,求出包含城市xi (1 ≤ xi ≤ n)的区域中的最大路径的长度。
- 2 习一。这是Andrew向Dima提出的请求,将包含城市xi的区域和包含城市yi的区域合并(1 ≤ xi, yi ≤ n)。请注意,xi 可以等于 yi。

输出

对于第一种类型的每个事件,将答案打印在单独的行上。

示例

输入 #1

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

输出 #1

4