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 Abecome 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

The first line contains two integers n and m (1 ≤ n ≤ 22; ) — 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

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.

题目大意

给定一些关系(u,v)代表两个人是朋友。每次可以选择一个人i，使i的朋友都相互变成朋友。问最少需要选择多少人，使得所有的人都能够相互认识。

 #include<bits/stdc++.h>

 const int INF = 0x3f3f3f3f;

 const int maxn = ;

 int n,m,ans,id;

 struct node

 {

     int val,vis[maxn],pr[maxn],deg[maxn];

     std::bitset<maxn> mp[maxn];

     bool legal()

     {

         for (int i=; i<=n; i++)

             if (mp[i].count() < n) return ;

         return ;

     }

     void print()

     {

         for (int i=; i<=val; i++)

             printf("%d ",pr[i]);

         puts("");

     }

 }now,tmp,chg;

 std::queue<node> q;

 int read()

 {

     char ch = getchar();

     int num = ;

     bool fl = ;

     for (; !isdigit(ch); ch=getchar())

         if (ch=='-') fl = ;

     for (; isdigit(ch); ch=getchar())

         num = (num<<)+(num<<)+ch-;

     if (fl) num = -num;

     return num;

 }

 int main()

 {

     freopen("party.in","r",stdin);

     freopen("party.out","w",stdout);

     n = read(), m = read(), now.val = , ans = INF;

     for (int i=; i<=n; i++) now.mp[i][i] = ;

     for (int i=; i<=m; i++)

     {

         int u = read(), v = read();

         now.mp[u][v] = , now.mp[v][u] = ;

     }

     q.push(now);

     while (q.size())

     {

         tmp = q.front(), q.pop();

         if (tmp.legal()){

             ans = tmp.val;

             printf("%d\n",ans);

             tmp.print();

             break;

         }

         bool fnd = ;

         while (!fnd){

         id = ;

         for (int i=; i<=n; i++)

             if (!tmp.vis[i]){

                 tmp.deg[i] = tmp.mp[i].count();

                 if (tmp.deg[i] > tmp.deg[id]) id = i;

             }

         for (int i=; i<=n; i++)

             if (tmp.deg[i]==tmp.deg[id]){

                 bool upd = ;

                 chg = tmp, chg.val++;

                 chg.vis[i] = , chg.pr[chg.val] = i;

                 for (int j=; j<=n; j++)

                     for (int k=; k<=n; k++)

                         if (j!=k&&chg.mp[i][j]&&chg.mp[i][k]&&!chg.mp[j][k])

                             chg.mp[k][j] = chg.mp[j][k] = , upd = ;

                 if (upd) fnd = , q.push(chg);

                 else tmp.vis[i] = ;

             }

         }

     }

     return ;

 }

 #include<bits/stdc++.h>

 const int maxn = ;

 const int maxs = ;

 const int INF = 0x3f3f3f3f;

 bool fnd;

 int n,m,mx;

 int s[maxn],f[maxs],fa[maxs],pr[maxs];

 int read()

 {

     char ch = getchar();

     int num = ;

     bool fl = ;

     for (; !isdigit(ch); ch=getchar())

         if (ch=='-') fl = ;

     for (; isdigit(ch); ch=getchar())

         num = (num<<)+(num<<)+ch-;

     if (fl) num = -num;

     return num;

 }

 void fndScheme(int st)

 {

     if (fa[st]) fndScheme(fa[st]);

     printf("%d ",pr[st]);

 }

 int main()

 {

 //    freopen("party.in","r",stdin);

 //    freopen("party.out","w",stdout);

     memset(f, 0x3f3f3f3f, sizeof f);

     n = read(), m = read(), mx = (<<n)-;

     for (int i=; i<n; i++) s[i+] = <<i;

     for (int i=; i<=m; i++)

     {

         int x = read()-, y = read()-;

         s[x+] |= <<y, s[y+] |= <<x;

     }

     fnd = ;

     for (int i=; i<=n; i++)

     {

         f[s[i]] = , pr[s[i]] = i;

         if (s[i]!=mx) fnd = ;

     }

     if (fnd){

         puts("");

         return ;

     }

     for (int st=; st<=mx; st++)

         if (f[st]!=INF){

             for (int i=; i<=n; i++)

                 if (((st>>(i-))&)&&(f[st]+ < f[st|s[i]])){

                     f[st|s[i]] = f[st]+;

                     fa[st|s[i]] = st;

                     pr[st|s[i]] = i;

                 }

         }

     printf("%d\n",f[mx]);

     fndScheme(mx);

     return ;

 }