An và Bình chơi một trò chơi trên cây có \(N\) nút. Một quân cờ được đặt ở nút 1 (gốc). Mỗi lượt, người chơi di chuyển quân cờ từ nút hiện tại sang một nút kề cạnh chưa được ghé thăm trước đó. Người nào không thể di chuyển được sẽ thua. Cả hai đều chơi tối ưu.

Hãy xác định người thắng cuộc.

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

• Dòng đầu chứa số nguyên \(N\) (\(1 \le N \le 10^5\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) (\(1 \le u, v \le N\)) là một cạnh của cây.

Định dạng đầu ra

• In ra \(1\) nếu An (người đi trước) thắng, \(2\) nếu Bình thắng.

Ví dụ

Input:

5
1 2
1 3
2 4
2 5

Output:

1

Ràng buộc