Hợp nhất rừng cây và đường kính

General
Points
75
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Cho $N$ đỉnh rời rạc (ban đầu chưa có cạnh nào). Thực hiện $Q$ thao tác thuộc hai loại:

  • 1 u v: nối đỉnh $u$ và $v$ bằng một cạnh độ dài $1$ (nếu $u$ và $v$ đã cùng thành phần liên thông thì bỏ qua).
  • 2 u: in ra đường kính hiện tại (số cạnh của đường đi đơn dài nhất) trong thành phần liên thông chứa đỉnh $u$.
Dữ liệu vào

Dòng đầu chứa hai số nguyên $N, Q$. $Q$ dòng tiếp theo, mỗi dòng là một thao tác dạng 1 u v hoặc 2 u.

Dữ liệu ra

Với mỗi thao tác loại 2, in ra kết quả trên một dòng.

Ví dụ
Input Output
5 6
1 1 2
2 1
1 2 3
1 4 5
2 3
2 4
1
2
1
Giới hạn

$1 \le N, Q \le 10^5$, $1 \le u, v \le N$.

Draft saved