BT đang chơi một trò chơi gọi tên 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 hai chiều. Các thành phố đá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,\ldots,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ó một đường đi kết nối hai thành phố này.
Các câu hỏi của trò chơi có dạng:

• 1 x: Chiều dài đường đi dài nhất trong vùng chứa thành phố x?
• 2 x y: Nếuthành phố x nằm trong cùng một vùng với thành phố y thì không làm gì cả. 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 và nối chúng bằng một con đường sao cho chiều dài của đường đi dài nhất (với các đỉnh không lặp lại) trong vùng hợp nhất là ngắn nhất. 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ỳ trong số chúng.

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<n; 1\leq q \leq 3\times 10^5)\) tương ứng là số thành phố, số con đường đã có và số câu hỏi.
• Mỗi dòng trong m dòng tiếp theo chứa hai số nguyên \(a_i\) và \(b_i\) (\(a_i\neq b_i;1\leq a_i,b_i\leq n\)) mô tả một con đường nối hai thành phố \(a_i\) và \(b_i\). Có nhiều nhất một con đường nối hai thành phố
• Mỗi dòng trong số \(q\) dòng tiếp theo chứa một câu hỏi có một trong hai dạng sau:
  • "1 \(x_i\)": Xác định chiều dài của đường đi dài nhất trong vùng chứa thành phố \(x_i\) (\(1\leq x_i\leq n\)). Dữ liệu đảm bảo luôn có ít nhất một câu hỏi dạng này.
  • "2 \(x_i\) \(y_i\)": Hợp nhất vùng chứa thành phố \(x_i\) và vùng chứa thành phố \(y_i\) (\(1\leq x_i,y_i\leq n\)). Chú ý rằng \(x_i\) có thể bằng \(y_i\).

Output

• Với mỗi câu hỏi dạng thứ nhất, ghi câu trả lời 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