Eulerian Cycles
---------------

A Eulerian cycle is a closed path in an undirected graph
that includes every edge exactly once.  The path may be
non-simple: it may visit a particular vertex many times.
It is easy to show that a graph has an Eulerian cycle if
and only if the graph is connected and every vertex of
the graph has even degree.  Here the degree of a vertex
is the number of edges of which the vertex is an end-
point.

You have been asked to find an Eulerian cycle in each
of several connected graphs.  Some of the graphs are
very large.

Input 
-----

For each of several test cases, first a line containing
just the test case name, then M lines each containing a
representation of an edge of the form

	<vertex> - <vertex>
	
and lastly a line containing just `*'.  Here <vertex>
is just an integer in the range 1, ..., N where N is
the total number of vertices in the graph.

No edge will be represented more than once.

        3 <= N <= 100,000.
	N - 1 <= M <= 1,000,000

All input graphs are guaranteed to be connected and all
vertices in these graphs are guaranteed to have even
degree.

Input ends with an end of file.


Output
------

For each test case, just two lines, the first containing
an exact copy of the test case name input line, and the
second a possibly very long line containing the list of
vertices visited by an Eulerian cycle, in the order of
visitation.  There should be exactly M + 1 vertices in
this list with the first vertex being repeated at the
end of the list.  Any one of the many possible Eulerian
cycles may be output.


Sample Input
------ -----

-- 5 VERTEX COMPLETE GRAPH --
1 - 2
1 - 3
1 - 4
1 - 5
2 - 3
2 - 4
2 - 5
3 - 4
3 - 5
4 - 5
*
-- 6 VERTEX REGULAR DEGREE 4 GRAPH --
1 - 2
1 - 3
2 - 3
2 - 4
3 - 4
3 - 5
4 - 5
4 - 6
5 - 6
5 - 1
6 - 1
6 - 2
*


Sample Output
------ ------

-- 5 VERTEX COMPLETE GRAPH --
2 4 3 2 5 1 4 5 3 1 2
-- 6 VERTEX REGULAR DEGREE 4 GRAPH --
1 2 6 4 2 3 1 6 5 3 4 5 1



File:	   eulerian.txt
Author:	   Bob Walton <walton@seas.harvard.edu>
Date:	   Sat Oct 12 00:23:41 EDT 2013

The authors have placed this file in the public domain;
they make no warranty and accept no liability for this
file.

RCS Info (may not be true date or author):

    $Author: walton $
    $Date: 2013/10/12 05:04:54 $
    $RCSfile: eulerian.txt,v $
    $Revision: 1.5 $