题目描述

题目译自 XX Olimpiada Informatyczna — I etap Multidrink

Bajtazar 居住在以奶吧闻名的 Bajtow，每处路口都有一家奶吧。一天，他突发奇想，决定进行「奶吧多饮」之旅，逐一造访每家奶吧，且每家仅一次。Byteasar 希望规划一条路线，确保下一家奶吧始终与前一家相距不超过两条街道。

Bajtow 的路口编号从 $1$ 到 $n$，所有街道双向通行，任意两路口间有唯一路径，不重复经过任何路口。Bajtazar 从路口 $1$ 出发，最终到达路口 $n$。

你的任务是找出一条满足 Bajtazar 要求的路线，或确认无此类路线。

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

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

输入格式

第一行包含一个整数 $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$。

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

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

数据范围与提示

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