题意

道路系统可以看作是一片森林。为了高效地存储各个连通分量，我们需要使用并查集（DSU）。首先，需要构建初始的道路系统。对于初始道路系统中的每个连通分量，我们必须求出该分量的直径。这可以通过 DFS 或 BFS 实现。

设 $a$ 为分量中的任意一个顶点。
设 $b$ 为距离顶点 $a$ 最远的顶点。
设 $c$ 为距离顶点 $b$ 最远的顶点。
直径等于 $b$ 到 $c$ 的距离。这个求直径的算法只对树结构有效。
对于并查集中的每个分量，我们记录其直径。

思路

现在处理第 $1$ 类查询就非常简单了：找到顶点 $x$ 所属的分量，并输出该分量的直径。
第 $2$ 类查询也很容易处理：设 $u$ 为顶点 $x$ 所在的分量，$v$ 为顶点 $y$ 所在的分量。如果 $u \neq v$，则我们可以合并这两个分量。新分量的直径按如下方式计算：

[ \text{new_diameter} = \max\left( \text{diameter}_u,\ \text{diameter}_v,\ \left\lceil \frac{\text{diameter}_u}{2} \right\rceil + \left\lceil \frac{\text{diameter}_v}{2} \right\rceil + 1 \right) ]

算法步骤

1. 读入初始道路信息，使用并查集维护连通分量。
2. 对每个连通分量，任选一个顶点 $a$，通过 DFS/BFS 找到距离 $a$ 最远的顶点 $b$。
3. 再从 $b$ 出发，通过 DFS/BFS 找到距离 $b$ 最远的顶点 $c$，$b$ 到 $c$ 的距离即为该分量的直径。
4. 将直径信息保存在并查集的根节点中。
5. 对于第 $1$ 类查询，直接输出对应分量的直径。
6. 对于第 $2$ 类查询，若两个顶点不在同一分量，则按上述公式合并并更新直径。

复杂度分析

时间复杂度为 $O(n \cdot \alpha(n))$，其中 $\alpha(n)$ 是反阿克曼函数（inverse Ackermann function）。

代码说明

• 使用并查集（DSU）维护连通分量及其直径。
• 使用两次 DFS/BFS 求树的直径。
• 合并时按公式计算新直径，并更新并查集根节点信息。
• 查询时直接通过并查集找到根节点并输出直径。