题目描述

幼儿园里的孩子们经常争吵，这让保育员非常头疼。比如，在吃饭时，如果一对彼此敌对的孩子坐在一起，就容易爆发激烈冲突。虽然每轮围坐在圆桌旁的孩子数量并不多，但他们之间的“敌人”或“朋友”关系可能非常复杂。

保育员很想安排一种合适的座次，使得任何一对彼此为“敌人”的孩子都不相邻。现在需要你帮助她设计一种合理的围坐安排。

我们知道一共有 $2n$ 个孩子围坐在一个圆桌旁，而且任何一个孩子的“敌人”不超过 $n-1$ 个。

输入格式

输入包含若干组测试数据，每组数据格式如下：

第一行两个整数 $n$ 和 $m$，其中 $1 \leq n \leq 200$，$0 \leq m \leq n(n - 1)$；

接下来 $m$ 行，每行两个不同的整数 $i$ 和 $j$（$1 \leq i,j \leq 2n$，$i \ne j$），表示第 $i$ 个孩子与第 $j$ 个孩子是“敌人”；

输入块之间有一个空行；

输入以一行 $0\ 0$ 结束，该行不需要处理。

输出格式

对于每一组测试数据：

如果存在一种合法的围坐方案，使得所有敌对关系的两人不相邻，则输出一种满足条件的顺时针座位安排，$2n$ 个数字，用空格隔开；

如果不存在合法安排，输出 No solution!。

1 0

2 2
1 2
3 4

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

4 12
1 2
1 3
1 4
2 5
2 6
3 7
3 8
4 8
4 7
5 6
5 7
6 8

0 0

1 2
4 2 3 1
1 6 3 2 5 4
1 6 7 2 3 4 5 8