#P2195. HXY造公园
HXY造公园
题目描述
现在有一个现成的公园,有 个休息点和 条双向边连接两个休息点。众所周知,HXY 是一个 SXBK 的强迫症患者,所以她打算施展魔法来改造公园并即时了解改造情况。她可以进行以下两种操作:
- 对某个休息点 ,查询公园中可以与该点互相到达的休息点组成的路径中的最长路径。
- 对于两个休息点 ,如果 已经可以互相到达则忽略此次操作。否则,在 可到达的所有休息点和 可到达的所有休息点(包括 自身)分别选择一个休息点,然后在这两个休息点之间连一条边,并且这个选择应该满足对于连接后的公园, 和 所在的区域(即 可达到的所有休息点和边组成的集合)中的最长路径的长度最小。
HXY打算进行 个操作,请你回答她的对于公园情况的询问(操作 1)或者执行她的操作(操作 2)。
注:所有边的长度皆为 。保证不存在环。最长路径定义为:对于点 ,如果对于其中任意的 和 ,都有边相连接,那么 所在区域的最长路径就是 。
输入格式
- 第一行,三个正整数,分别为 。
- 接下来的 行,每一行有两个正整数 ,表示 和 有一条双向边相连。
- 再接下来的 行,每一行表示一个操作。
- 若该行第一个数为 ,则表示操作 1,之后还有一个正整数 ,表示要查询的休息点。
- 若该行第一个数为 ,则表示操作 2,之后还有两个正整数 ,表示需要执行操作的两个休息点。
输出格式
输出行数为操作 1 的个数。
每行输出对于操作 1 询问的回答。
6 0 6
2 1 2
2 3 4
2 5 6
2 3 2
2 5 3
1 1
4
提示
数据范围及约定
- 对于 的数据,只存在操作 1。
- 对于 的数据,,。
- 对于 的数据,,。
- 对于 的数据,,。