I'm from Tabriz!

Hadi Moshayedi

Sattar Khan, the governor of Tabriz, wants to make tourist information centers in some junctions of the city. He wants to do this in a way that at least one of two junctions at the end of each street have a tourist information center. He asked Hadi to decide which junctions should have tourist information centers so the least number of tourist information centers are built. Hadi asks you to help him! Please note that Tabriz has neither more than one street between two distinct junctions nor a street from a junction to itself.

Input

The first line of input gives the number of cases, N (at most 20). N test cases will follow. Each one starts with two lines containing the number of junctions n<=30, and number of streets of the city m. Each of next m lines contains two numbers: si and ti (0<=si, ti < n) indicating that there is a street between si-th junction and ti-th junction.

Output

For each test case, your program must output the line containing "Case #x: ", followed by minimum number of tourist information centers which should be built. Next line must contain the list of junctions in which a tourist information center should be built. As there might be many valid solutions, your program can print any of them. In the case there was no junction selected, output a blankline as the second line of testcase output.

Case #1: 2
3 4
Case #2: 1
0

1st Amirkabir UT Annual Programming Contest  Qualification Round