20 · Welcome24ever 和公园

题目描述

现在有一个现成的公园，有 $n$ 个休息点和 $m$ 条双向边连接两个休息点（所有边长度均为 $1$）。这些点和边构成一片森林（保证不存在环）。 Welcome24ever 是一个强迫症患者，她打算施展魔法来改造公园并即时了解改造情况。她可以进行以下两种操作： 1. 对某个休息点 $x$，查询当前公园中与 $x$ 互相可达的所有休息点构成的连通块中，最长简单路径的长度（即该连通块的直径）。 2. 对于两个休息点 $x,y$，如果当前它们已经处在同一个连通块中，则忽略此次操作；否则： - 各自从 $x$ 所在连通块与 $y$ 所在连通块中分别任选一个休息点（可以选 $x,y$ 本身）用一条新边连接； - 该条新边长度为 $1$； - 选择的这两个休息点应使得新连通块的最长路径长度尽可能小。 Welcome24ever 一共会进行 $q$ 个操作，请你依次回答所有操作 1 的询问结果（操作 2 只会改变结构，不输出）。 注： 所有边长度均为 $1$。 对于一个连通块，如果它的最长路径经过点列 $v_1, v_2, \dots, v_k$（相邻两点之间有边），则该连通块的最长路径长度为 $k-1$。

第一行，三个正整数 $n,m,q$。 接下来 $m$ 行，每行两个正整数 $x_i,y_i$，表示 $x_i$ 和 $y_i$ 之间有一条双向边。 接下来 $q$ 行，每行描述一个操作： - 若行首为 1 ，则为操作 1，后跟一个整数 $x_i$； - 若行首为 2 ，则为操作 2，后跟两个整数 $x_i,y_i$。 保证初始图无环（是一片森林）。

对每个操作 1 输出一行一个整数，表示该点所在连通块当前的最长路径长度。

输入 #1

输出 #1