题目描述

有一个由 \(n\) 个点，\(m\) 条边组成的图，有 \(q\) 组询问。

\(1.\) 1 x，给出点 \(x\)，输出点 \(x\) 的树的直径；
\(2.\) 2 x y，选择任意两点 \(u,v\)，使得 \(u\) 跟 点 \(x\) 在同一棵树中且 \(v\) 跟 点 \(y\) 在同一棵树中。将 \(u,v\) 之间连一条边，使得连边后的到的新树的直径最小。当然，如果 \(x,y\) 在同一棵树中则忽略此操作。

格式

输入格式

第一行三个整数 \(n,m,q\)，分别表示 点的个数，边的个数和询问个数；
接下来 \(m\) 行，每行两个整数 \(x,y\)，表示有一条链接点 \(x,y\) 的边；
接下来 \(q\) 行，每行表示一条操作。

输出格式

输出行数为操作 \(1\) 的个数；
每行一个整数表示对应的操作一的答案。

样例1

样例输入1

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

样例输出1

4

限制

\(1 \le m < n \le 3× 10^5\)

\(1 \le q \le 3 × 10^5\)