Lớp học có \(N\) học sinh, giữa một số cặp là bạn thân ngồi cạnh nhau (tạo thành cấu trúc cây). Cô giáo muốn chọn ra một nhóm học sinh đi thi văn nghệ sao cho không có hai bạn nào ngồi cạnh nhau trong nhóm.

Hãy tìm số lượng học sinh lớn nhất có thể chọn.

\(|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ố học sinh lớn nhất có thể chọn.

Đị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 số lượng đỉnh tối đa trong một tập độc lập của cây.

Ví dụ

Input:

5
1 2
1 3
1 4
1 5

Output:

4

Giải thích: Chọn tập các lá {2, 3, 4, 5} gồm 4 đỉnh không có cạnh nối giữa chúng.

Ràng buộc & Subtasks