Cuarto Online

PROBLEM F

THE SWEEPER IN CLEANLAND

Cleanland is a city well-known for the civility of its inhabitants. There is no crime, the streets are clean, drivers respect speed limits. In spite of its cleanliness, every day, during the early hours of the morning, a machine is used to clean the curb sides of each street. The city is not too large, so every street is a two-way street, and there is only one machine available to do the job of sweeping the streets. Both sides of each street must be swept. The operator of the sweeping machine is a inhabitant of the city, therefore the curb is traversed in the direction the traffic flows, so each street must be traversed in both directions, cleaning one side at a time.

Your job is to provide the operator with an optimal route, so that no street is traversed more than twice, once in each direction. Of course, one may drive from any point in the city to any other point in that same town. For simplicity, we assume that every street is one block in length, connecting two distinct corners. The figure below gives a small example one such town, where is an optimal route.

Input

The input contains several test cases, each case consists of two or more lines. The first line contains two integers, n and m, separated by one space. Integer n, (2<=n<=100), is the number of corners, which are identified by the integers 0, 1, . . . , n−1. Integer m, (0 < m <= n(n−1)/2), is the number of streets. The next m lines describe the m streets: every line contains two integers v and w, separated by one space, corresponding to the corners connected by the street. Note that no two corners are connected by two or more streets. Note also that the ends of each street are distinct. The end of the input is indicated by a line containing precisely two zeros, separated by one space.

Output

For each test case, your program should output one line. The line contains case c: followed by one space, where c is the case number, without leading zeros (the first case is case number 1). Then, separated by precisely one space, an optimal route, described by its corners, in the order they appear in the route. You should not repeat the initial corner as the last corner. All these integers should be printed in the same line, separated by exactly one space. 

Sample Input

6 7

0 1

0 5

1 2

1 5

2 3

2 4

3 4

2 1

0 1

0 0 

Sample Output

case 1: 2 3 4 2 4 3 2 1 0 5 1 5 0 1

case 2: 0 1

Notice:

Figure 1: An optimal route: 2 3 4 2 4 3 2 1 0 5 1 5 0 1