Trường học tổ chức đêm vũ hội. Có \(N\) học sinh, giữa một số cặp học sinh có mối quan hệ bạn bè thân thiết, tạo thành cấu trúc cây. Ban tổ chức muốn ghép các cặp nhảy sao cho mỗi học sinh chỉ tham gia tối đa một cặp, và hai học sinh trong cùng cặp phải là bạn thân của nhau.

Hãy tìm số cặp nhảy nhiều nhất có thể tổ chức.

\(|1| \le 20\) | 10 | \(|2| \le 5000\) | 20 | \(|3| \le 2 \cdot 10^5\) | 30 | \(|4| \le 2 \cdot 10^5\) | 40 |

Đầu vào:

• Dòng đầu gồm \(N\). - N - \(1\) dòng sau, mỗi dòng gồm \(u, v\).

Đầu ra:

• Một số nguyên là số cặp nhảy lớn nhất.

Định dạng đầu vào

• Dòng 1: Số nguyên \(N\) (\(1 \le N \le 10^5\)). - N-\(1\) dòng tiếp theo: mỗi dòng chứa 2 số nguyên \(u, v\) mô tả một cạnh.

Định dạng đầu ra

• In ra kích thước của cặp ghép cực đại (số cạnh lớn nhất không chung đỉnh).

Ví dụ

Input:

4
1 2
2 3
3 4

Output:

2

Giải thích: Chọn 2 cạnh \((1, 2)\) và \((3, 4)\).

Ràng buộc & Subtasks