Nền văn minh

BT đang chơi một trò chơi gọi là "Nền văn minh". Bạn hãy giúp BT chơi trò chơi đó.

Trò chơi có \(n\) thành phố và \(m\) con đường vô hướng. Các thành phố được đánh số từ \(1\) đến \(n\). Giữa hai thành phố bất kỳ hoặc có một đường đi duy nhất hoặc không có đường đi nào cả. Một đường đi là một dãy các thành phố khác nhau \(v_1, v_2, ..., v_k\) sao cho giữa hai thành phố liên tiếp \(v_i\) và \(v_{i+1}\) \((1 \leq i < k)\) có một con đường nối chúng. Chiều dài của đường đi này bằng \(k-1\).

Chúng ta nói rằng hai thành phố cùng một vùng khi và chỉ khi có đúng một đường đi kết nối hai thành phố này.

BT muốn trả lời hai loại truy vấn sau:

• "1 x": Tìm chiều dài đường đi dài nhất trong vùng chứa thành phố \(x\).
• "2 x y": Kiểm tra xem thành phố \(x\) và thành phố \(y\) có cùng một vùng hay không. Nếu không, BT cần phải hợp nhất hai vùng như sau: chọn một thành phố trong vùng thứ nhất và một thành phố trong vùng thứ hai, nối chúng bằng một con đường sao cho chiều dài của đường đi dài nhất trong vùng hợp nhất là nhỏ nhất có thể. Nếu có nhiều cách làm như vậy, bạn được phép chọn một cách bất kỳ.

Bạn hãy giúp BT trả lời các câu hỏi loại 1 và thực hiện các yêu cầu loại 2.

Input

• Dòng đầu tiên chứa ba số nguyên \(n, m, q\) \((1 \leq n \leq 3 \times 10^5; 0 \leq m \leq n; 1 \leq q \leq 3 \times 10^5)\) --- số thành phố, số con đường ban đầu và số truy vấn.
• Mỗi trong số \(m\) dòng tiếp theo chứa hai số nguyên \(a_i\) và \(b_i\) \((1 \leq a_i, b_i \leq n, a_i \neq b_i)\) --- mô tả một con đường nối hai thành phố \(a_i\) và \(b_i\). Có thể có nhiều nhất một con đường nối hai thành phố.

• Mỗi trong số \(q\) dòng tiếp theo chứa một truy vấn thuộc một trong hai dạng:

• "1 x": Xác định chiều dài của đường đi dài nhất trong vùng chứa thành phố \(x\) \((1 \leq x \leq n)\). Dữ liệu đảm bảo luôn có ít nhất một truy vấn dạng này.

• "2 x y": Hợp nhất vùng của thành phố \(x\) và vùng của thành phố \(y\) \((1 \leq x, y \leq n, x \neq y)\).

Output

Với mỗi câu hỏi dạng thứ nhất, in ra kết quả trên một dòng.

Example

10 3 9
1 2
1 3
2 4
1 2
2 1 1
2 7 9
2 3 2
2 2 7
2 2 5
1 6
2 7 4
1 7

3
0
4