在几何课上，老师画了一个圆，圆上有很多条弦，这些弦两两不重合，但是 有些是相交的。你本想把图临摹下来回家好好研究，可惜下课后，图被值日生 擦掉了。幸运的是，你准确地记录了弦的数量和弦的相交情况。
现在，你想尽量复原这张图。同时你还想知道，最多能选出多少条弦，使得 选出来的弦两两不相交。

第一行包含2个正整数n,m，分别表示弦的条数以及相交弦的对数，所有的弦从1至n编号。接下来 m行每行两个正整数a,b，表示第a条弦与第b条弦相交。

输出分为两行。
第一行输出2n个正整数，按逆时针方向给出满足题意的圆上每条弦的两个
端点的相对顺序，其中第i条弦的两个端点均用数字i来表示。
第二行输出1个正整数，表示最多能选多少条两两不相交的弦。

1<=N<=20 1<=M<=40

vfleaking提供spj

//表示只会10分暴力

//对大神的位运算优化膜拜。

#include<cstdio>

#include<cstring>

#include<iostream>

using namespace std;

const int N=;

const int M=1.5e6+;

int n,m,len,cnt,bin[N],lg[M],f[M],q[N],mp[N],pth[N<<],ans[N<<];

bool a[N][N],vis[N];int sum,end;

inline void Max(int &x,int y){if(x<y) x=y;}

bool dfs(int k,int goal){

    if(k>goal) return ;

    len++;

    for(int i=len;i;i--) pth[i]=pth[i-];

    for(int i=;i<=len;i++){

        pth[i]=k;len++;

        for(int j=len;j>i+;j--) pth[j]=pth[j-];

        for(int j=i+,s=;j<=len;j++){

            pth[j]=k;

            if(!(s^mp[k]) && dfs(k+,goal)) return ;

            pth[j]=pth[j+];

            s^=bin[pth[j]-];

        }

        len--;pth[i]=pth[i+];

    }

    len--;

    return ;

}

int bfs(int S){

    int h=,t=;len=;q[t]=S;vis[S]=;

    while(h!=t){

        int x=q[++h];

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

            if(!vis[i] && a[x][i]){

                vis[i]=;

                q[++t]=i;

            }

        }

    }

    for(int j=;j<=t;j++){

        mp[j]=;

        for(int k=;k<j;k++){

            if(a[q[j]][q[k]]) mp[j]|=bin[k-];

        }

    }

    return t;

}

void work(){

    for(int i=;i<=len;i++) ans[++cnt]=q[pth[i]];

    for(int i=;i<=end;i++){

        mp[i]=bin[i-];

        for(int j=;j<=end;j++){

            if(a[q[i]][q[j]]){

                mp[i]|=bin[j-];

            }

        }

    }

    int mx=,tot=bin[end]-;

    memset(f,,sizeof f);

    for(int j=tot,x;j;j--){

        mx=max(mx,f[j]);

        for(int k=j;k;k^=x){

            x=k&-k;

            Max(f[j&(tot^mp[lg[x]+])],f[j]+);

        }

    }

    sum+=max(mx,f[]);

}

int main(){

    scanf("%d%d",&n,&m);

    for(int i=,x,y;i<=m;i++) scanf("%d%d",&x,&y),a[x][y]=a[y][x]=;

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

    for(int i=;i<=bin[n];i++) lg[i]=lg[i>>]+;

    for(int i=;i<=n;i++) if(!vis[i]){

        end=bfs(i);

        dfs(,end);

        work();

    }

    for(int i=;i<=cnt;i++) printf("%d%c",ans[i],(i<cnt)?' ':'\n');

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

    return ;

}