Problem K
Sneaky Exploration
You have been sent to spy on the city of Galcary. When you arrive, you realize with shock that the Galcarians are far more efficient than you first expected. Every pair of buildings in Galcary are connected by some sequence of roads (roads go between two buildings), and the Galcarians have built the minimum number of roads possible to achieve this. You decide you must learn more by visiting every building.
You may start and end in any building you wish, but you may not visit the same building twice as you are on a strict schedule. Your method of choice to avoid detection is flying between buildings. If you fly over a road built by the Galcarians, the risk of detection by Galcary’s anti-spy force is too high. So you may not travel directly between buildings connected by a road.
Input
The first line of input contains a single integer
It is guaranteed that all buildings are connected to all other buildings by some sequence of roads.
Output
If there is a way to explore Galcary adhering to the
specifications above, print any such exploration on one line -
this takes the form of
If there is no such way to explore Galcary, output a single
integer
Sample Input 1 | Sample Output 1 |
---|---|
4 1 2 2 3 3 4 |
3 1 4 2 |
Sample Input 2 | Sample Output 2 |
---|---|
4 1 2 2 3 2 4 |
-1 |
Sample Input 3 | Sample Output 3 |
---|---|
5 1 2 2 3 2 5 3 4 |
2 4 5 3 1 |