Bài 4. Đường kính đồ thị (3,0 điểm)

Cho một đồ thị vô hướng gồm N đỉnh (được đánh số từ 1 đến N) và M cạnh, không chứa chu trình (tức đồ thị là một rừng gồm các cây), không có cạnh nối mỗi đỉnh với chính nó, giữa hai đỉnh chỉ có nhiều nhất một cạnh nối.

Khoảng cách giữa hai đỉnh thuộc cùng một thành phần liên thông là số cạnh trên đường đi ngắn nhất giữa chúng. Đường kính của một thành phần liên thông được định nghĩa là khoảng cách lớn nhất giữa hai đỉnh bất kỳ trong thành phần đó.

Có Q truy vấn thuộc một trong hai loại sau:

• Loại 1 (1 x): Cho biết đường kính của thành phần liên thông chứa đỉnh x.
• Loại 2 (2 x y): Thêm đúng một cạnh nối một đỉnh thuộc thành phần liên thông chứa đỉnh x với một đỉnh thuộc thành phần liên thông chứa đỉnh y sao cho đường kính của thành phần liên thông mới tạo thành là nhỏ nhất có thể. Nếu x và y đã thuộc cùng một thành phần liên thông thì bỏ qua thao tác này.

Lưu ý: Sau mỗi thao tác Loại 2 hợp lệ, cạnh mới thêm vào sẽ được giữ nguyên cho các thao tác tiếp theo.

Yêu cầu: Hãy xử lý tuần tự Q thao tác và in ra kết quả tương ứng với mỗi thao tác Loại 1.

Dữ liệu

Vào từ file văn bản DIA.INP:

• Dòng đầu chứa ba số nguyên N, M, Q (với 1 <= N <= 310^5, 0 <= M < N, 1 <= Q <= 310^5).
• M dòng tiếp theo, mỗi dòng chứa hai số nguyên u, v (1 <= u, v <= N, u != v) mô tả một cạnh nối giữa đỉnh u và đỉnh v.
• Q dòng tiếp theo, mỗi dòng mô tả một thao tác theo định dạng 1 x hoặc 2 x y (1 <= x, y <= N). Các số trên cùng một dòng cách nhau bởi dấu cách.

Kết quả

Ghi ra file văn bản DIA.OUT:

• Với mỗi thao tác Loại 1, in ra trên một dòng một số nguyên duy nhất là kết quả tìm được.

Ví dụ

Chấm điểm

• Subtask 1 (25% số điểm): Đồ thị thỏa mãn luôn tồn tại đường đi giữa mọi đỉnh (đồ thị liên thông ban đầu). Có đúng một truy vấn dạng Loại 1: 1 x;
• Subtask 2 (25% số điểm): N, Q <= 2000;
• Subtask 3 (25% số điểm): Không có thao tác Loại 2 (chỉ gồm các thao tác truy vấn Loại 1);
• Subtask 4 (25% số điểm): Không có ràng buộc gì thêm.