
 0通过
 2提交
 题目提供者 洛谷
 评测方式 云端评测
 标签 图论 构造 POI 2013 高性能
 难度 尚无评定
 时空限制 1000ms / 128MB
最新讨论 显示
题目描述
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 .
输入输出样例
说明
给一棵树，每次步伐大小只能为1或2，要求不重复的遍历n个节点，且起点为1，终点为n