트리 부수기

$0$번부터 $N-1$번까지 $N$개의 노드를 가진 트리가 주어진다. 두 노드 $u$와 $v$에 대하여 $c(u,v)$를 다음과 같이 정의하자.

$u$번 노드와 연결된 모든 간선을 제거한 뒤에도 $0$번 노드와 $v$번 노드를 잇는 경로가 존재하면 $c(u,v)$는 $1$이고, 그렇지 않으면 $0$이다.

$1 \leq x \leq N-1$을 만족하는 정수 $x$에 대하여, $N-1$자리 이진수로 표현되는 함수 $f(x)$를 다음과 같이 정의하자.

$f(x) = \left( c(x, N-1)c(x, N-2)\dots c(x, 1) \right)_{(2)}$

예시로 주어진 아래의 트리에서 $f(3)$의 값을 구해보자.

$3$번 노드와 연결된 모든 간선을 제거한다. 이때 $0$번 노드에서 $4$번 노드로 가는 경로는 없으므로 $c(3,4)=0$이다. 반면 $0$번 노드에서 $1$번 노드로 가는 경로는 남아 있으므로 $c(3,1)=1$이다. 같은 방법으로 나머지 값을 구하면 $f(3)={00011}_{2}$이다.

이제 다음 값을 구해보자.

$f(1) \oplus f(2) \oplus \cdots \oplus f(N-2) \oplus f(N-1)$

$\oplus$는 비트별 배타적 논리합 연산자이다. 자세한 설명은 여기를 참고하라.

첫 번째 줄에 노드의 개수 $N$이 주어진다. ($3 \leq N \leq 200\,000$)

두 번째 줄부터 $N-1$개의 줄에 걸쳐 트리의 각 간선이 잇는 두 노드의 번호 $u$, $v$가 공백으로 구분되어 주어진다. ($0 \leq u,v \leq N-1$; $u \neq v$)

$f(1) \oplus f(2) \oplus \cdots \oplus f(N-2) \oplus f(N-1)$의 값을 $N-1$자리 이진수로 출력한다.

가장 오른쪽 비트는 $c(1, 1) \oplus c(2, 1) \oplus \dots \oplus c(N-1, 1)$이다. 출력 순서에 유의하라.