분자 결합의 방향 정하기

크로아티아의 한 화학 실험실에서 분자 사이의 화학 결합을 연구한다. 지금 다루는 대상은 질소 수소 적층 화합물의 분자 무리다.

이 화합물은 분자 $N$개가 공유 결합 $N-1$개로 묶여 있고, 모든 분자가 결합을 따라 직접 또는 간접으로 이어져 하나의 구조를 이룬다.

연구진은 모든 공유 결합을 방향이 있는 결합으로 바꾸려고 한다. 새로 만든 화합물은 불안정해서 각 분자에서 임펄스가 아주 많이 나오고, 임펄스는 방향이 있는 결합을 따라 다른 분자로 이동한다. 임펄스는 결합에 정해진 방향으로만 그 결합을 지날 수 있다.

화합물의 불안정도는 임펄스 하나가 이동하면서 지날 수 있는 결합의 최대 개수다. 연구진은 화합물이 가장 안정하도록, 즉 불안정도가 최소가 되도록 결합의 방향을 정하려고 한다.

공유 결합마다 방향을 정하라.

첫째 줄에 분자의 개수 $N$이 주어진다. ($2 \le N \le 100\,000$)

이어지는 $N-1$개의 줄에 정수 $a_i$와 $b_i$가 주어진다. ($1 \le a_i, b_i \le N$) 분자 $a_i$와 분자 $b_i$가 공유 결합으로 이어져 있다는 뜻이다. 주어지는 결합은 언제나 트리를 이룬다.

$N-1$개의 줄을 출력한다. $i$번째 줄에는 입력의 $i$번째 결합의 방향을 적는다. 결합이 $a_i$에서 $b_i$로 향하면 1을, $b_i$에서 $a_i$로 향하면 0을 출력한다.

불안정도가 최소인 방향 배정은 여러 가지이므로, 다음 규칙으로 정한 배정 하나만 정답으로 인정한다. 분자 1에서 각 분자까지의 거리를 지나는 결합의 개수로 재고, 모든 결합을 거리가 짝수인 쪽 분자에서 거리가 홀수인 쪽 분자로 향하게 한다. 결합으로 이어진 두 분자는 거리가 정확히 1만큼 차이 나므로 방향은 하나로 정해진다.