Description

There is an existing park with $n$ rest spots and $m$ undirected edges connecting pairs of rest spots. As everyone knows, HXY is an OCD patient of "SXBK", so she plans to use magic to renovate the park and instantly keep track of the renovation. She can perform the following two operations:

1. For a rest spot $x$, query the longest path within the set of rest spots that are mutually reachable with $x$.
2. For two rest spots $x, y$, if $x$ and $y$ are already mutually reachable, ignore this operation. Otherwise, choose one rest spot from all rest spots reachable from $x$ and one rest spot from all rest spots reachable from $y$ (including $x$ and $y$ themselves), then add one edge between these two chosen rest spots. This choice should minimize, in the park after the connection, the length of the longest path within the region containing $x$ and $y$ (that is, the set consisting of all rest spots and edges reachable from $x$ and $y$).

HXY plans to perform $q$ operations. Please answer her queries about the park (operation 1) or carry out her operation (operation 2).

Note: All edges have length $1$. It is guaranteed that there are no cycles. The longest path is defined as follows: for vertices $v_1, v_2, \cdots, v_k$, if for every $v_i$ and $v_{i+1} \ (1 \le i \le k-1)$ there is an edge connecting them, then the longest path in the region containing any $v_j \ (1 \le j \le k)$ has length $k - 1$.

Input Format

• The first line contains three positive integers $n, m, q$.
• The next $m$ lines each contain two positive integers $x_i, y_i$, indicating that there is an undirected edge between $x_i$ and $y_i$.
• The next $q$ lines each describe an operation.
  • If the first number is $1$, this is operation 1; then there is one positive integer $x_i$, the rest spot to query.
  • If the first number is $2$, this is operation 2; then there are two positive integers $x_i, y_i$, the two rest spots for the operation.

Output Format

The number of output lines equals the number of operation 1.

On each line, output the answer to the corresponding operation 1 query.

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

4

Hint

Constraints and Conventions

• For $10\%$ of the testdata, only operation 1 exists.
• For $30\%$ of the testdata, $0 \le m < n \le 20$, $1 \le q \le 5$.
• For $60\%$ of the testdata, $0 \le m < n \le 2000$, $1 \le q \le 1000$.
• For $100\%$ of the testdata, $0 \le m < n \le 3 \times 10^5$, $1 \le q \le 3 \times 10^5$.

Translated by ChatGPT 5