GIRTH - Lazy tourist guide


Marie-Chantal 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 Marie-Chantal 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: 2021-02-10 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: 2018-12-02 13:42:33

hello

shubham_001: 2017-06-30 15:02:55

shouldn't it be 3 1 2 4 1 ?

amit_gh: 2017-05-13 22:15:53

Shouldn't the condition be 1≤A<B≤N ? Also, can someone explain the case 2 solution?


Added by:xtof
Date:2016-11-08
Time limit:1s-4s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU