#P2195. HXY造公园

    ID: 1213 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>搜索图论并查集广度优先搜索BFS树的直径

HXY造公园

题目描述

现在有一个现成的公园,有 nn 个休息点和 mm 条双向边连接两个休息点。众所周知,HXY 是一个 SXBK 的强迫症患者,所以她打算施展魔法来改造公园并即时了解改造情况。她可以进行以下两种操作:

  1. 对某个休息点 xx,查询公园中可以与该点互相到达的休息点组成的路径中的最长路径。
  2. 对于两个休息点 x,yx,y,如果 x,yx,y 已经可以互相到达则忽略此次操作。否则,在 xx 可到达的所有休息点和 yy 可到达的所有休息点(包括 x,yx,y 自身)分别选择一个休息点,然后在这两个休息点之间连一条边,并且这个选择应该满足对于连接后的公园,xxyy 所在的区域(即 x,yx,y 可达到的所有休息点和边组成的集合)中的最长路径的长度最小。

HXY打算进行 qq 个操作,请你回答她的对于公园情况的询问(操作 1)或者执行她的操作(操作 2)。

注:所有边的长度皆为 11。保证不存在环。最长路径定义为:对于点 v1,v2vkv_1,v_2\cdots v_k,如果对于其中任意的 viv_ivi+1(1ik1)v_{i+1}\quad (1\le i\le k-1),都有边相连接,那么 vj(1jk)v_j\quad(1\le j\le k) 所在区域的最长路径就是 k1k-1

输入格式

  • 第一行,三个正整数,分别为 n,m,qn,m,q
  • 接下来的 mm 行,每一行有两个正整数 xi,yix_i,y_i,表示 xix_iyiy_i 有一条双向边相连。
  • 再接下来的 qq 行,每一行表示一个操作。
    • 若该行第一个数为 11,则表示操作 1,之后还有一个正整数 xix_i,表示要查询的休息点。
    • 若该行第一个数为 22,则表示操作 2,之后还有两个正整数 xi,yix_i,y_i,表示需要执行操作的两个休息点。

输出格式

输出行数为操作 1 的个数。

每行输出对于操作 1 询问的回答。

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

提示

数据范围及约定

  • 对于 10%10\% 的数据,只存在操作 1。
  • 对于 30%30\% 的数据,1m<n201\le m<n\le 201q51\le q\le5
  • 对于 60%60\% 的数据,1m<n20001\le m<n \le 20001q10001\le q\le 1000
  • 对于 100%100\% 的数据,1m<n3×1051 \le m<n \le 3\times 10^51q3×1051\le q\le 3\times 10^5