Trang trại của Farmer John gồm \(N\) đồng cỏ (\(2\leq N\leq 10^5\)) được nối bởi \(N-1\) con đường sao cho có thể đi từ bất kỳ đồng cỏ nào đến bất kỳ đồng cỏ nào khác. Nói cách khác, trang trại là một cây. Nhưng sau 28 năm xử lý những bài toán thuật toán hóc búa chắc chắn nảy sinh từ cây, FJ đã quyết định rằng một trang trại có dạng cây đơn giản là quá phức tạp. Ông tin rằng các bài toán thuật toán sẽ đơn giản hơn trên các đường đi.

Vì vậy, kế hoạch của ông là phân hoạch tập hợp các con đường thành nhiều đường đi và giao trách nhiệm về mỗi đường đi cho một người làm công xứng đáng. Để tránh tranh chấp, ông muốn mọi đường đi có cùng độ dài. Ông tự hỏi với những độ dài nào thì tồn tại một cách phân hoạch như vậy.

Chính xác hơn, với mỗi \(1\leq K\leq N-1\), hãy giúp Farmer John xác định liệu có thể phân hoạch các con đường thành những đường đi có độ dài đúng bằng \(K\) hay không.

Phân nhóm

• Trong các test 2-4, cây có dạng hình sao; nhiều nhất một đỉnh có bậc lớn hơn hai.
• Các test 5-8 thỏa mãn \(N\le 10^3\).
• Các test 9-15 không có ràng buộc bổ sung.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên \(N\).

Mỗi dòng trong \(N-1\) dòng tiếp theo chứa hai số nguyên \(a\) và \(b\) cách nhau bởi dấu cách, mô tả một cạnh nối đỉnh \(a\) với đỉnh \(b\). Cả \(a\) và \(b\) đều thuộc đoạn \(1\ldots N\).

Dữ liệu ra

In một xâu bit có độ dài \(N-1\). Với mỗi \(1\le K\le N-1\), bit thứ \(K\) tính từ bên trái của xâu bằng 1 nếu có thể phân hoạch các cạnh của cây thành những đường đi có độ dài đúng bằng \(K\), và bằng \(0\) nếu không thể.

Ví dụ

13
1 2
2 3
2 4
4 5
2 6
6 7
6 8
8 9
9 10
8 11
11 12
12 13

111000000000

Nguồn

USACO 2020 February Contest, Gold - Delegation: https://usaco.org/index.php?page=viewproblem2&cpid=1019

Tác giả: Mark Gordon và Dhruv Rohatgi.