P3549 [POI 2013] 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  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

无

无

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