Cho ~ n ~ địa điểm ~ (2≤n≤10^5) ~ kết nối với nhau bởi ~ n-1 ~ con đường hai chiều, sao cho từ một địa điểm có thể tới bất kỳ địa điểm nào khác. Nói cách khác, các địa điểm này hình thành nên một cây. Yêu cầu đặt ra là chia cây đã cho thành nhiều cây con, sao cho đường đi trong mỗi cây con này có chiều dài bằng nhau. Cụ thể, cho ~ 1 ≤ k < n ~, liệu có tồn tại cách phân chia tập các con đường hai chiều, thành nhiều tập con các con đường hai chiều, sao cho chúng tạo thành đường đi có chiều dài bằng ~ k ~, đưa ra 1 nếu tồn tại, đưa ra 0 nếu không tồn tại.

Dữ liệu vào

• Dòng đầu tiên gồm số nguyên ~ n ~.
• ~ n-1 ~ dòng tiếp theo gồm hai số nguyên ~ a ~ và ~ b ~ mô tả một cạnh nối giữa hai đỉnh ~ a ~ và ~ b ~, ~ a ~ và ~ b ~ nằm trong đoạn ~ [1..n] ~

Kết quả

Đưa ra dãy bit có chiều dài ~ n-1 ~. Với mỗi ~ 1 ≤ k < n ~, tính từ trái qua phải, bit thứ ~ k ~ sẽ bằng 1 nếu có thể phân chia, bằng 0 nếu không thể phân chia

Ví dụ:

Input 1

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 

Output 1

111000000000 

** Giải thích:** Ta có thể phân chia cây thành đường đi có chiều dài K, với K=1,2,3. Với K=3, ta có thể phân chia như sau: 13−12−11−8,10−9−8−6,7−6−2−3,5−4−2−1