Delegation (Gold)

Farmer John의 농장은 $N$개의 목초지($2 \leq N \leq 10^5$)가 $N-1$개의 도로로 이어져 있어서, 어느 목초지에서든 다른 모든 목초지로 갈 수 있다. 즉 이 농장은 트리다. FJ는 28년 동안 트리에서 생기는 까다로운 알고리즘 문제를 다뤄 왔는데, 트리 모양의 농장은 너무 복잡하다고 판단했다. 그는 알고리즘 문제가 경로 위에서는 더 단순하다고 믿는다.

그래서 도로 집합을 여러 개의 경로로 나누고, 각 경로를 일꾼 한 명에게 맡기려 한다. 일꾼들 사이의 다툼을 막으려고 모든 경로의 길이가 같아야 한다. 어떤 길이에 대해 이런 분할이 가능할까?

각 $1 \leq K \leq N-1$에 대해, 도로를 길이가 정확히 $K$인 경로들로 나눌 수 있는지 판정하라.

첫 줄에 정수 $N$이 주어진다. 이어지는 $N-1$개의 줄에는 목초지 $a$와 $b$를 잇는 간선을 나타내는 정수 $a$, $b$가 주어진다. $a$와 $b$는 모두 $1$ 이상 $N$ 이하이다.

길이가 $N-1$인 비트열을 출력한다. 왼쪽에서 $K$번째 비트는 도로를 길이가 정확히 $K$인 경로로 나눌 수 있으면 1, 없으면 0이다.

이 트리는 $K=1,2,3$일 때 길이 $K$인 경로로 나눌 수 있다. $K=3$일 때 가능한 경로 분할은 13-12-11-8, 10-9-8-6, 7-6-2-3, 5-4-2-1 이다.