Party
Contest: Технокубок 2018 - Отборочный Раунд 4
Difficulty rating: 2400
Tags: brute force, graphs

Arseny likes to organize parties and invite people to it. However, not only friends come to his parties, but friends of his friends, friends of friends of his friends and so on. That's why some of Arseny's guests can be unknown to him. He decided to fix this issue using the following procedure.

At each step he selects one of his guests A, who pairwise introduces all of his friends to each other. After this action any two friends of A become friends. This process is run until all pairs of guests are friends.

Arseny doesn't want to spend much time doing it, so he wants to finish this process using the minimum number of steps. Help Arseny to do it.

Input format:
The first line contains two integers n and m (1 ≤ n ≤ 22; $$0 \leq m \leq \frac{n(n-1)}{2}$$) — the number of guests at the party (including Arseny) and the number of pairs of people which are friends.

Each of the next m lines contains two integers u and v (1 ≤ u, v ≤ n; u ≠ v), which means that people with numbers u and v are friends initially. It's guaranteed that each pair of friends is described not more than once and the graph of friendship is connected.

Output format:
In the first line print the minimum number of steps required to make all pairs of guests friends.

In the second line print the ids of guests, who are selected at each step.

If there are multiple solutions, you can output any of them.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case there is no guest who is friend of all other guests, so at least two steps are required to perform the task. After second guest pairwise introduces all his friends, only pairs of guests (4, 1) and (4, 2) are not friends. Guest 3 or 5 can introduce them.

In the second test case guest number 1 is a friend of all guests, so he can pairwise introduce all guests in one step.

Example input:
5 6
1 2
1 3
2 3
2 5
3 4
4 5

Example output:
2
2 3

Example input:
4 4
1 2
1 3
1 4
3 4

Example output:
1
1

Editorial:
Let’s formulate and prove several facts.
1. If we change an call order, the result doesn’t change. Let’s consider two vertices which are called consecutively. If they are not connected by edge, then regardless of the order, we get that at the end, neighbours of each vertex form a clique.
If they are connected, then independently on the order, we get clique from 2 vertices and all neighbours of them.
2. If graph is a tree, it’s sufficient to take as an answer all its vertices except leaves. Indeed, if we consider any 2 tree vertices, we get that all vertices on the way between them are in the answer. Each vertex reduces on 1 the distance between those 2, it means that the distance between them is 1.
3. Let’s select from source graph spanning tree, that has the largest number of leaves. One can say that we can use all vertices except leaves as an answer.
Obviously from point 2, that after all our operations with such set graph will become complete. Let’s show that it is minimal number of vertices.
Let we selected some set of vertices, that is the answer. Then subgraph of given graph, built on the selected set of vertices, should be connected (otherwise between connected component can’t appear the edge and graph can’t be complete. Also, each of vertices, that isn’t in an answer should have at least one of neighbours selected (otherwise it is impossible to add new edge to it). Now let’s select a spanning tree in selected set (it’s possible because our set is connected) and add non-selected vertices into the tree as leafs. Then we see that our selected can be represented as spanning tree in the initial graph, in which all selected vertices are all non-leaf vertices and possibly, some leafs; but leafs can be obviously removed from the selected set by proved above. So, one of optimal answers can be described as set of non-leaf vertices of spanning tree with minimal possible number of non-leaves and, as a consequence, with maximal possible number of leaves, QED.
4. Implementation. It is necessary to implement an algorithm that should work for 2n·n or faster or with worse asymptotic but with non-asymptotical optimization. One of possible solutions is following. Let contain any subset of vertices as a n-bit mask; for example, mask of a subset containing vertices {v1, v2, ..., vk} will be equal to 2v1 + 2v2 + ... + 2vk. Then, for subset with mask m, vertex v is in set iff m & 2v is not equal to 0; here & is a bitwise AND.
Let for each vertex v, neighbours[v] be a mask of subset of vertices containing vertex v and it's neighbours. Array neighbours[v] can be calculated easily. Then, let bool isConnected[m] be 1 for some mask m iff subset coded by m is connected. Array isConnected can be calculated in O(2n * n) by the following algorithm:
• for all vertices $$v \in [0..n-1]$$ (let vertices be enumerated in 0-indexation), isCalculated[2v] is assigned to 1; for all other masks, isCalculated should be equal to 0;
• then, go through all masks in increasing order by a simple cycle; let m be current mask in the cycle;
• if isConnected[m] = 0, then go to the next iteration of cycle;
• otherwise, let v1, v2, ..., vk be vertices of subset coded by m. Then, mask m':  = maskNeighbours[m]:  = neighbours[v1]|neighbours[v2]|... |neighbours[vk] for | as bitwise OR is a mask coding a subset of vertices containing vertices of mask m and their neighbours. Then, for each vertex w in subset of mask m' we assign isConnected[m|2w] to be 1.
The described algorithm works in O(2n * n); it can be proved by induction that at the end, isConnected[m] = 1 for mask m iff m is a code of connected subset of vertices.
But how to find an answer? Notice that mask m = 2v1 + 2v2 + ... + 2vk is a code of good (for our purposes) subset iff isConnected[m] = 1 and maskNeighbours[m] = 2n - 1 = 20 + 21 + ... + 2n - 1. For each mask m, we can check if it's good in O(n) time having an array isConnected calculated; the answer is a good mask with minimal possible number of elements in the corresponding set.