Tý có một khu chung cư có \(N\) căn hộ được nối với nhau bởi \(N - 1\) hành lang. Ban quản lý muốn lắp đặt camera an ninh tại một số căn hộ sao cho mỗi hành lang đều có ít nhất một đầu được lắp camera.

Hãy tìm số lượng camera ít nhất cần lắp đặt.

\(|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ố camera tối thiểu.

Đị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 thiểu trong một tập phủ đỉnh của cây.

Ví dụ

Input:

4
1 2
2 3
3 4

Output:

2

Giải thích: Chọn tập đỉnh {2, 3} sẽ phủ toàn bộ các cạnh \((1, 2)\), \((2, 3)\), \((3, 4)\).

Ràng buộc & Subtasks