[POI2013]MUL-Multidrink

题目描述

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 ![](http://main.edu.pl/images/OI20/mul-en-tex.1.png) to ![](http://main.edu.pl/images/OI20/mul-en-tex.2.png), 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. ![](http://main.edu.pl/images/OI20/mul-en-tex.3.png) and finishes at the intersection no. ![](http://main.edu.pl/images/OI20/mul-en-tex.4.png). Your task is to find any route that satisfies Byteasar's requirements if such a route exists. An exemplary route satisfying the requirements is: ![](http://main.edu.pl/images/OI20/mul-en-tex.5.png) 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 ![](http://main.edu.pl/images/OI20/mul-en-tex.6.png) (![](http://main.edu.pl/images/OI20/mul-en-tex.7.png)), denoting the number of intersections in Byteburg. Each of the following ![](http://main.edu.pl/images/OI20/mul-en-tex.8.png) lines holds a pair of distinct integers ![](http://main.edu.pl/images/OI20/mul-en-tex.9.png) and ![](http://main.edu.pl/images/OI20/mul-en-tex.10.png) (![](http://main.edu.pl/images/OI20/mul-en-tex.11.png)), separated by a single space, that represent the street linking the intersections no. ![](http://main.edu.pl/images/OI20/mul-en-tex.12.png) and ![](http://main.edu.pl/images/OI20/mul-en-tex.13.png). In tests worth ![](http://main.edu.pl/images/OI20/mul-en-tex.14.png) of all points the condition ![](http://main.edu.pl/images/OI20/mul-en-tex.15.png) 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 ![](http://main.edu.pl/images/OI20/mul-en-tex.16.png) lines to the standard output, the ![](http://main.edu.pl/images/OI20/mul-en-tex.17.png)-th of which should contain the number of the ![](http://main.edu.pl/images/OI20/mul-en-tex.18.png)-th intersection on an arbitrary route satisfying Byteasar's requirements. Obviously, in that case the first line should hold the number ![](http://main.edu.pl/images/OI20/mul-en-tex.19.png), and the ![](http://main.edu.pl/images/OI20/mul-en-tex.20.png)-th line - number ![](http://main.edu.pl/images/OI20/mul-en-tex.21.png).

输入输出样例

输入样例 #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

说明

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