404641: GYM101597 D Effective network

Quite recently, in a very close galaxy cluster, there was a bunch of planets. As the galaxy expands to a vast space, the only effective way of traveling between them is to use the network of teleporters. Due to technological problems, one can only travel between certain pairs of teleporters, using so-called links. This means that in order to travel from planet A to planet B, one may need to first teleport from A to some intermediate planet before reaching B. The distance between planets A and B is the minimum number of links required to travel between them. It is guaranteed that one can travel between each pair of planets using a finite number of links, but this number may be quite large for some pairs.

You are an employee of Teleport GmbH and were tasked to set up terms and conditions for the GA Travel Card such that the customers are happy. In order to do this, you need to select a non-empty subset of planets, called promoted planets, and designate all the links between them (and only those) to be included in the GA. We will call these free links. Thanks to customer survey you know that there are three conditions you need to fulfill:

• There should be at least two promoted planets.
• It should be possible to travel between any two promoted planets A and B using only free links
• The distance between any two promoted planets A and B, using only free links, cannot be larger than R - K, where R is the number of promoted planets, and K is a fixed constant representing the demands of the customers.

Determine whether it is possible to find a set of promoted planets, and if so, return one set that satisfies the conditions. If there are multiple solutions, return any of them.

First line contains integers 1 ≤ N ≤ 5000, , 1 ≤ K ≤ N – the number of planets, the number of links, and the height of the demands, respectively.

Next M lines contain description of links. Each link is represented by two integers, 1 ≤ u_i, v_i ≤ N, meaning that there is a link between planets u_i and v_i. It is guaranteed that no pair occurs more than once, and also that u_i ≠ v_i.

It is guaranteed that one can travel between each pair of planets using a finite number of links.

If there is a solution, output two lines: the first containing a single integer R – the number of promoted planets. On the second line, print R space separated integers, specifying the indices of promoted planets.

If there is no set of planets that would satisfy the conditions, output a single line containing the integer 0.

7 9 3
1 3
1 4
1 5
2 5
3 4
6 3
6 1
4 6
1 7

4
1 3 4 6

5 4 3
1 3
1 2
3 4
3 5

0

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

3
1 3 5

In the first sample case, we select a set of four planets that are all pairwise connected. As R = 4 and K = 3, the conditions are satisfied.

In the second test case, there is no subset of planets satisfying the conditions.

In the third case note that the pair of planets 1 and 5 would not be a solution, as one cannot travel between them without interchange at a non-promoted planet.