BZPRO
#3149. [Ctsc2013]复原
内存限制：128 MiB
时间限制：10 Sec
提交
提交记录
讨论
题目描述
在几何课上，老师画了一个圆，圆上有很多条弦，这些弦两两不重合，但是 有些是相交的。你本想把图临摹下来
回家好好研究，可惜下课后，图被值日生 擦掉了。幸运的是，你准确地记录了弦的数量和弦的相交情况。现在，
你想尽量复原这张图。同时你还想知道，最多能选出多少条弦，使得 选出来的弦两两不相交。
输入格式
第一行包含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
BZPRO