题目描述

题目译自 XX Olimpiada Informatyczna — I etap Multidrink

Bajtazar 居住在以奶吧闻名的 Bajtow 市，这里的每个路口都有一家奶吧。一天，他决定进行一次「奶吧多饮」之旅，逐一造访每个路口的奶吧，并且每个路口只经过一次。Bajtazar 希望规划一条路线，使得下一家奶吧始终与前一家相距不超过两条街道。

Bajtow 的路口编号从 $1$ 到 $n$，所有街道都是双向通行的，并且任意两个路口之间有且仅有一条简单路径（即整个城市是一棵树）。Bajtazar 从路口 $1$ 出发，最终到达路口 $n$。

你的任务是找出一条满足 Bajtazar 要求的路线，或者确认不存在这样的路线。

满足条件的路线示例为：1,11,8,7,5,9,2,10,4,6,3,12

不存在任何满足任务条件的路线。

---

示例

样例 1

输入：

12
1 7
7 8
7 11
7 2
2 4
4 10
2 5
5 9
2 6
3 6
3 12

输出：

1
11
8
7
4
10
2
9
5
6
3
12

样例 2

输入：

15
1 14
14 7
7 8
7 11
7 2
2 4
4 10
2 5
5 9
2 6
3 6
3 15
11 12
8 13

输出：

BRAK

---

输入格式

• 第一行包含一个整数 $n$ ($2 \leq n \leq 500000$)，表示 Bajtow 的路口数量。
• 接下来的 $n-1$ 行，每行包含两个不同的整数 $a_i, b_i$ ($1 \leq a_i, b_i \leq n$)，表示连接路口 $a_i$ 和 $b_i$ 的街道。

---

输出格式

• 如果不存在满足 Bajtazar 要求的路线，输出一行一个字符串 BRAK。
• 否则，输出 $n$ 行，第 $i$ 行包含路线第 $i$ 个路口的编号。第一行必须为 $1$，第 $n$ 行必须为 $n$。

---

数据范围与提示

• 对于 $65\%$ 的数据，$n \leq 5000$。