Powerful Strongholds

All submissions for this problem are available.

[Problem Idea : Varun Jalan and Yu Yiu Ho]

In a small world not so far away, there is an ongoing war between two nations, A and B. There are n (3 n 20) strongholds in this world, with roads between some of them. Two strongholds are neighbors if there is a road between them, all roads are bidirectional. The Chef is at war and he recently came up with a scheme that will help his country to never lose the war. He would like to select a set of powerful strongholds (defined below) of minimum size and conquer those strongholds to ensure that his country will never be defeated. A set of powerful strongholds is a set of strongholds S, such that

1.For every stronghold y which does not belong to S, there is a road leading to it from a stronghold x which belongs to S. This way, any stronghold not in S is threatened by a stronghold in S.

2.S can properly defend (defined next) any attack from strongholds outside of S.

The mechanism for attacking and defending S is defined as follows:

i.In an attack, each single stronghold y not belonging to S will select one of its neighbor z belonging to S (if any) to attack. In this case y is an attacker of z.

ii.Given the attack routes of all y not belonging to S, each stronghold x belonging to S may decide to defend one of its neighbors, say z, in which case x is a defender of z. Alternatively, x may decide to defend itself, in which case x is a defender of x.

iii.The attack can be properly defended if there exists a defend route such that at every stronghold z belonging to S, there are at least as many defenders of z as attackers of z.

The rationale is that once the Chef occupies the strongholds in S, any other stronghold is immediately within reach of S by a single road (rule 1), and S will never be overwhelmed by attacks from outside (rule 2), and thus the Chef will never lose a stronghold in S. In order to make the task of occupying S easier, it is best if S is as small as possible. The Chef has given you the task to identify the smallest set of powerful strongholds so that he can proceed with his plan.

Input:

There will be multiple test cases. Each test case is a specification of the strongholds and roads. For each test case, there will be one line containing n (3 <= n <= 20), the number of strongholds, and r (0 <= r <= 190), the number of roads. Then, the next r lines each contains two integers x and y giving a road between stronghold x and y. The strongholds are numbered from 0 to n-1. There is a blank line following each test case. The last test case is followed by a line containing two zeros (after the blank line).

Output:

For each test case, output a single line of integers. The first integer is |S|, represents size of the smallest possible set of powerful strongholds. The next |S| integers give one such possible set of strongholds. If there are multiple possible answers for S, output the lexicographically smallest one.

Sample Input:

3 2
0 1
1 2

6 6
0 1
1 2
2 3
3 4
4 5
5 0

5 10
0 1
0 2
0 3
0 4
1 2
1 3
1 4
2 3
2 4
3 4

0 0

Sample Output:

2 0 1
4 0 1 2 3
3 0 1 2