Hyacinth 주파수 배정

Hyacinth라고 부르는 다중 채널 메시 네트워크 구조에서는 무선 메시 네트워크의 각 노드에 네트워크 인터페이스 카드(NIC)가 정확히 두 개 있다. NIC마다 주파수를 하나씩 정한다. 서로 통신 범위 안에 있는 두 노드는 NIC에 같은 주파수가 하나 이상 있어야 통신하므로, 한 노드가 쓰는 주파수는 최대 두 개다.

서로 통신 범위 안에 있는 두 노드가 같은 주파수를 함께 쓰고 있으면 그 주파수는 사용 중이다. 네트워크에서 사용 중인 주파수가 많을수록 이론상 처리량이 좋다. 서로 통신 범위 안에 있는 모든 노드 쌍이 통신할 수 있도록 $2n$개의 NIC에 주파수를 배정하고, 사용 중인 주파수의 개수를 최대로 만들어라. 네트워크의 연결 관계는 트리를 이룬다.

첫째 줄에 네트워크의 노드 개수 $n$ ($2 \le n \le 10\,000$)이 주어진다.

다음 $n - 1$개 줄에는 두 정수 $i$와 $j$ ($1 \le i, j \le n$)가 주어진다. 노드 $i$와 노드 $j$가 서로 통신 범위 안에 있다는 뜻이다. 노드 번호는 1번부터 $n$번까지이고, 주어진 연결 관계는 트리를 이룬다.

$n$개 줄을 출력한다. $i$번째 줄에는 노드 $i$의 NIC 두 개에 배정한 주파수를 출력한다. 주파수는 $10^9$보다 작은 음이 아닌 정수다.

최댓값을 만드는 배정은 여러 가지이므로, 다음 규칙으로 만든 배정을 출력한다.

• 모든 노드의 인접 목록을 번호가 작은 순서로 정렬하고, 1번 노드를 루트로 삼는다.
• 주파수는 1, 2, 3, ... 순서로 꺼내 쓴다. 0은 어떤 간선에도 쓰이지 않는 NIC를 뜻한다.
• 1번 노드의 이웃이 하나뿐이면 그 간선에 주파수 1을 준다. 이웃이 둘 이상이면 번호가 가장 작은 이웃으로 가는 간선에 주파수 1을 주고, 1번 노드의 나머지 간선에는 모두 주파수 2를 준다.
• 1번 노드에서 시작해 방문하지 않은 이웃 중 번호가 가장 작은 쪽으로 먼저 내려가는 깊이 우선 탐색을 한다. 1번이 아닌 노드 $v$에 처음 도착했을 때 $v$에 자식이 있으면, 아직 꺼내지 않은 가장 작은 주파수를 $v$와 자식을 잇는 모든 간선에 준다.
• $i$번째 줄에는 노드 $i$가 참여하는 주파수 두 개를 작은 값부터 출력한다. 노드 $i$가 주파수 하나에만 참여하면 첫 번째 값은 0이다.