시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 1024 MB62191534.091%

문제

Farmer John의 충성스러운 농노 준원이는 정점이 N개인 완전 그래프를 키우고 있었다. 준원이는 그래프에 희망이라는 이름을 붙이고, 매일 산책시켜 주며 예뻐해 주었다. 희망이의 각 정점에는 0 이상 109 이하의 정수가 하나씩 적혀있고, 서로 다른 두 정점 사이에는 간선이 하나씩 있었다. 희망이의 각 간선의 가중치는 간선이 잇는 두 정점에 쓰인 두 수를 XOR한 값이었다.

그림 1. 희망이의 생전 모습. 간선의 가중치는 간선이 잇는 두 정점에 쓰인 두 수의 XOR 값이다.

하지만 어제 Bessie가 일으킨 혁명으로 모든 것이 무너져버렸다. 준원이와 희망이는 다행히 지하 벙커로 대피하는 데 성공한 줄 알았지만, 잠시 한눈을 판 사이 준원이가 발견한 것은 유언장과, 권총으로 자살한 희망이의 시체였다. 준원이는 희망이의 앙상한 최소 스패닝 트리(Minimum Spanning Tree)를 조용히 묻어주었다.

그림 2. 희망이의 시체. 통통하던 희망이의 모습은 사라지고 앙상한 MST만이 남아있다.

여기서 여러분은 궁금할 것이다. 시체의 모습만을 보고, 원래 희망이의 각 정점에 무슨 수가 쓰여져 있었을지 알 수 있을까? 남아있는 최소 스패닝 트리에서, 각 정점의 차수(degree)는 모두 3 이하였다고 한다.

입력

첫째 줄에는 희망이의 정점의 개수 N이 주어진다. 편의상 각 정점을 1번에서 N번까지로 번호 붙이자.

이후 N-1개의 줄에는 희망이의 최소 스패닝 트리의 모양이 주어진다. 각 줄에는 최소 스패닝 트리의 각 간선이 잇는 두 정점의 번호가 공백을 사이에 두고 주어진다.

출력

원래 희망이의 1번 정점에서부터 N번 정점까지 N개의 정점에 적혀있었을 것으로 예상되는 N개의 정수들을 공백을 사이에 두고 차례대로 출력한다. 출력한 N개의 수들이 다음과 같은 문제의 조건들

  • 모두 0 이상 109 이하인 서로 다른 정수들이다.
  • 출력한 N개의 정수를 희망이의 각 정점에 적었을 때에, 입력으로 주어진 트리가 희망이의 최소 스패닝 트리가 될 수 있다(가능한 최소 스패닝 트리 중 하나이다).

을 만족한다면, 원래 희망이의 각 정점에 적혀있었던 수들과 다르더라도 정답으로 인정된다.

만약, 희망이의 각 정점에 어떤 수를 적더라도 위의 조건을 만족시킬 수 없다면, 대신 -1을 출력한다.

제한

  • 1 ≤ N ≤ 200,000
  • 주어지는 최소 스패닝 트리의 각 정점의 차수(degree)는 3 이하이다.

예제 입력 1

5
1 2
2 4
3 4
4 5

예제 출력 1

2 1 7 5 4

이 예제는 문제 윗부분에 있는 그림과 같다. 2 1 7 5 4 대신 5 4 2 6 7이나 13 9 4 1 2 등 어떤 답을 출력하더라도 문제의 조건을 만족한다면 정답으로 인정된다.