本题没有可用的提交语言。

题目背景

本题翻译为 AI 生成。

题目描述

Byteasar 住在 Byteburg，一座以每个街角都有牛奶吧而闻名的城市。某天，Byteasar 想出了一个“牛奶多饮计划”：他希望每个牛奶吧只去喝一次。理想情况下，他希望设计一条路线，使得每次前往下一个牛奶吧时，其距离上一个牛奶吧不会超过两个街区（即：路口）。

Byteburg 的路口从 $1$ 到 $N$ 编号，所有街道都是双向通行的。在每对路口之间，存在唯一的一条直接路径，即不会重复经过任何路口的路径。Byteasar 将从编号为 $1$ 的路口出发，并在编号为 $N$ 的路口结束。你的任务是找出一条满足 Byteasar 要求的任意路线（如果存在的话）。

输入格式

标准输入的第一行包含一个整数 $N$（$2 \leq N \leq 500000$），表示 Byteburg 中的路口数量。接下来的 $N - 1$ 行中，每行包含一对用一个空格分隔的不同整数 $A_i$ 和 $B_i$（$1 \leq A_i, B_i \leq N$），表示连接路口 $A_i$ 和 $B_i$ 的街道。

输出格式

如果不存在满足要求的路线，你的程序应在标准输出中输出一个单词“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