题目描述

Byteasar lives in Byteburg, a city famous for its milk bars on every corner.

One day Byteasar came up with an idea of a "milk multidrink": he wants to visit each milk bar for a drink exactly once.

Ideally, Byteasar would like to come up with a route such that the next bar is always no further than two blocks (precisely: intersections) away from the previous one.

The intersections in Byteburg are numbered from to , and all the streets are bidirectional.

Between each pair of intersections there is a unique direct route, ie, one that does not visit any intersection twice.

Byteasar begins at the intersection no. and finishes at the intersection no. .

Your task is to find any route that satisfies Byteasar's requirements if such a route exists.

An exemplary route satisfying the requirements is: There is no route that satisfies the requirements.

给一棵树，每次步伐大小只能为1或2，要求不重复的遍历n个节点，且起点为1，终点为n

输入格式

In the first line of the standard input there is a single integer (), denoting the number of intersections in Byteburg.

Each of the following lines holds a pair of distinct integers and (), separated by a single space, that represent the street linking the intersections no. and .

In tests worth of all points the condition holds.

输出格式

If there is no route satisfying Byteasar's requirements, your program should print a single word "BRAK" (Polish for none), without the quotation marks to the standard output. Otherwise, your program should print lines to the standard output, the -th of which should contain the number of the -th intersection on an arbitrary route satisfying Byteasar's requirements. Obviously, in that case the first line should hold the number , and the -th line - number .

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

提示

给一棵树，每次步伐大小只能为 1 或 2，要求不重复的遍历 $n$ 个节点，且起点为 $1$，终点为 $n$。无解输出 BRAK。

$n\le 500000$