In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].

If you are familiar with IRC chat, the support team is also reachable on PIRC network (`irc.pirc.pl`

) in `#szkopul`

channel. If you are not, just use email.

Please do not ask us things like "how to solve task XYZ?".

Please remember that the support team has to sleep sometimes or go to work in real life.

<Submit a solution> [0/100]**Task statistics**

Number of users: 123

Number of users with 100 points: 82

Average result: 77.5691

# Multidrink

### Memory limit: 256 MB

## Input

## Output

## Example

Number of users: 123

Number of users with 100 points: 82

Average result: 77.5691

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.

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 .

For the input data:

12 1 7 7 8 7 11 7 2 2 4 4 10 2 5 5 9 2 6 3 6 3 12

the correct result is:

1 11 8 7 4 10 2 9 5 6 3 12

For the input data:

15 1 14 14 7 7 8 7 11 7 2 2 4 4 10 2 5 5 9 2 6 3 6 3 15 11 12 8 13

the correct result is:

BRAK

*Task authors: Jakub Radoszewski, Wojciech Rytter.*