Farmer John cho mỗi bò một điện thoại để khuyến khích giao tiếp. Cần trạm phát trên $N$ đồng cỏ ($1 \le N \le 10,000$), đánh số $1,\ldots,N$, để tất cả liên lạc.

Đúng $N-1$ cặp kề nhau; mọi $A$, $B$ ($1 \le A \le N; 1 \le B \le N; A \ne B$) có dãy đồng cỏ kề nhau bắt đầu ở $A$, kết thúc ở $B$. Trạm chỉ đặt trong đồng cỏ và phủ đồng đó cùng tất cả đồng kề.

Tìm số trạm ít nhất để phủ mọi đồng.

Dữ liệu vào

Đọc từ đầu vào chuẩn.

• Dòng 1: số nguyên $N$.
• Các dòng $2,\ldots,N$: cặp kề, số nguyên $A$, $B$ cách nhau bởi dấu cách.

Dữ liệu ra

Ghi ra đầu ra chuẩn.

• Dòng 1: số nguyên, số trạm ít nhất.

Ví dụ

Dữ liệu vào 1

5
1 3
5 2
4 3
3 5

Dữ liệu ra 1

2

Ghi chú

5 đồng: 1 và 3, 5 và 2, 4 và 3, 3 và 5 kề nhau. Hình học như sau (hoặc tương tự):

               4  2
               |  |
            1--3--5

Có thể đặt ở 2 và 3 hoặc 3 và 5.

Tác giả: Jeffrey Wang, 2007