GIRTH  Lazy tourist guide
MarieChantal works as a tourist guide. As such she proposes tours to tourists in her city that pass by some of the available points of interest. In the city one can reach of course any point of interest from any other point of interest, but some for some pair of points it is unreasonable to walk directly from the first to the second point without stopping on the way at some other intermediate points of interest. The city provided MarieChantal a list of pairs of points of interest that is reasonable to reach directly. These pairs are called reasonable. If A, B is a reasonable pair then so is B, A.
A reasonable tour is a list of points of interest that are all different except the first and the last one which are equal, and such that any two successive points of interest on the list form a reasonable pair.
She is quite a lazy tourist guide so she wants to find a reasonable tour that visits as little points of interest as possible. Can you help her?
Input
The first line contains a single integer, the number of test cases.
Each test case starts with a line containing two space separated integers N and M, (1≤N≤1000, 1≤M≤40000) where N is the number of points of interest, numbered from 1 to N and M is the number of reasonable pairs. The remaining M lines contain each two space separated integers A, B, (1≤A<B≤N) describing a reasonable pair of interest. The pairs will be all distinct.
Output
For each test case, numbered k start at 1, output a single line as follows.
If there is no tour output "Case #k: 1". Otherwise output "Case #k: t u1 u2 … ut", where t is the length of an arbitrary shortest tour and u1, u2, … ut, the identifiers of the points of interest along the tour with u1 being equal to ut. The sequence u1, u2, ..., ut should be lexicographically smallest among all reasonable tours of length t.
Example
Input:
2
4 3
1 2
1 3
1 4
4 5
1 2
2 3
3 4
1 4
2 4
Output:
Case #1: 1
Case #2: 3 1 2 4 1
hide comments
Christoph Dürr:
20210210 22:56:32
Dear subham_001 and amit_gh, thank you for your corrections. I reacted very slowly. Probably I was a turtle in my previous life. 

ameernsr:
20181202 13:42:33
hello 

shubham_001:
20170630 15:02:55
shouldn't it be 3 1 2 4 1 ? 

amit_gh:
20170513 22:15:53
Shouldn't the condition be 1≤A<B≤N ? Also, can someone explain the case 2 solution? 
Added by:  xtof 
Date:  20161108 
Time limit:  1s4s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU 