Giải bài trực tuyến

Cho đồ thị G=(V,E) vô hướng liên thông không chu trình. Các đỉnh được đánh số từ 1 đến n. Tập hợp D được gọi là đại diện hoàn hảo của G nếu thỏa mãn:

• D là tập con của V.
• Với mỗi đỉnh u không thuộc D có đường nối trực tiếp từ u tới ít nhất 1 đỉnh trong D.
• D chứa ít phần tử nhất.

Cho đồ thị G. Hãy xác định |D|.

Input

Gồm nhiều bộ dữ liệu, mỗi bộ dữ liệu cho trên 1 nhóm dòng.:

• Dòng đầu tiên ghi n (1≤n≤1000)
• n-1 dòng tiếp theo, mối dòng ghi 2 số u,v mô tả một cạnh của đồ thị

Dữ liệu kết thúc bằng dòng chứa một số 0.

Output

Trên mỗi dòng ghi ra kết quả tương ứng với từng bộ dữ liệu.

Example

Input:
6
1 3
2 3
3 4
4 5
4 6
2
1 2
0

Output:
2
1