Byteasar 住在 Byteburg，这座城市以遍布街角的牛奶吧而闻名。有一天，Byteasar 想出了一个“牛奶多重饮”的点子：他想访问每家牛奶吧各一次。理想情况下，Byteasar 希望找到一条路线，使得下一个牛奶吧距离上一个牛奶吧不超过两个街区（准确地说是：路口）。

Byteburg 的路口编号从 $1$ 到 $n$，所有的街道都是双向的。在每对路口之间都存在唯一的直接路径，即不经过任何路口两次的路径。Byteasar 从 $1$ 号路口出发，在 $n$ 号路口结束。

你的任务是找到一条满足 Byteasar 要求的路线（如果存在的话）。

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

不存在满足要求的路线。

输入格式

标准输入的第一行包含一个整数 $n$ ($2 \le n \le 500\,000$)，表示 Byteburg 的路口数量。接下来的 $n-1$ 行，每行包含一对不同的整数 $a_{i}$ 和 $b_{i}$ ($1 \le a_{i}, b_{i} \le n$)，由空格分隔，表示连接 $a_{i}$ 和 $b_{i}$ 号路口的街道。

输出格式

如果不存在满足 Byteasar 要求的路线，程序应输出一个单词 "BRAK"（波兰语，意为“无”），不包含引号。否则，程序应输出 $n$ 行，第 $i$ 行应包含满足 Byteasar 要求的任意路线中第 $i$ 个路口的编号。显然，在这种情况下，第一行应为 $1$，第 $n$ 行应为 $n$。

样例

输入 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

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

输出 2

BRAK