487. Courier's Route

Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

There are N towns in a kingdom, numbered from 1 to N, with the capital having the number 1. Each town is enclosed in a city wall with 4 gates. The gates are also numbered, with the gates of the city i (1 ≤ iN) numbered 4· i-3, 4· i-2, 4· i-1, 4· i. At each gate is exactly one road that leads to some gate of another town (note that there may be more than one road between two towns). All the roads can be travelled in both directions. Due to a system of bridges and tunnels, the roads do not intersect outside the towns.

A royal courier has to post copies of an Important Royal Decree on the outer sides of all gates of all towns. The courier can freely move from one gate to another in any town, but outside of towns, he's allowed to travel only along the roads. The courier starts from the capital and has to return to the capital after completing the assignment.

Is it possible for the courier to do this, passing each gate exactly once? Exiting a town through a gate only to post the decree on the outer side of the gate and immediately returning to the town counts as passing the gate once.

The first line of the input file contains N (2 ≤ N ≤ 1000). Each of the following 2· N lines describes one road and contains two integers, separated by a space: the numbers of the two gates connected by the road.

The first line of the output file should contain the word "
" or "
" (without the quotes) depending on whether the courier's assignment can be completed while passing each gate exactly once. In case it is possible, the second line of the file should contain 4· N integers, separated by spaces: the numbers of the gates in the order the courier passes them. If there are several solutions, output any one of them.

sample input
sample output
1 9
2 10
3 13
4 8
5 11
6 14
7 16
15 12
1 3 13 14 16 15 12 9 10 11 5 6 7 8 4 2

Online Contester Team © 2002 - 2010. All rights reserved.