PEG Judge - WC02 - S - The Mines of Moria

Woburn Challenge 2002 - Suicidal

Problem 5: The Mines of Moria

Frodo was running frantically, mapping out his portion of the mines. In fact, all members of the Fellowship, barring Strider and Gimli, were doing the same.
But not out of laziness was Strider not participating - certainly not, given how honourable and courageous he was. Strider was busy preparing fasola mines. Those, once placed in a corridor, would explode as soon as anyone dared enter the mined corridor.

Gimli was quite busy too, huffing and chopping happily the dark mine walls - he was connecting all the corridors to create a path for Strider - who was to leave the mines - such that the latter could get through all of the corridors without re-entering a corridor where he had already placed a mine, for clearly, that would mean his demise.

The fellowship, while scouting the mines, worried about Strider. Just how did he plan to accomplish this task?
And yet, it was clear that the only thing that stood between the Fellowship and the yellow, crooked teeth of the monkey-like orcs of Moria was the fasolas...

We like Striker and don’t want him to die. Given the maps of the corridors returned by the members of the fellowship, design a path which would allow Strider to set the mines without getting himself killed. Also give the minimum number of corridors that must be dug by Gimli in order to complete the trail...

Oh yeah, some corridors may only be dug one way. Also, Gimli is easily confused and so he does not dig multiple corridors between intersections in the same direction. We guarantee that every test case will be solvable… You can thank us later.

Input

There will be multiple test cases.
Each test case begins with a single integer, the # of intersections (-1 denotes end of input) There will be no more than 200 intersections.
For each corridor, a line with two integers follows: intersection_i intersection_j (-1 -1 denotes end of corridors) - denotes corridor from i to j (one-based)
There will be no more than 10000 corridors.

Output

The first line should contain a single integer, the # of corridors created.
Following should be the path (a list of intersections starting from intersection 1 and ending at that intersection)