[Ctsc2013]复原

时间限制:10s      空间限制:128MB

题目描述

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


输入格式

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


输出格式

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


样例输入

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

样例输出

1 2 3 1 4 2 5 4 3 5
2

提示

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


题目来源

vfleaking提供spj

Menuappsclose