圆桌会议

Grade 100 Open Time Wednesday, 17 June 2020, 9:45 PM
Discount 0.8 Time Discount Wednesday, 17 June 2020, 9:45 PM
Allow late Yes Close Time Wednesday, 17 June 2020, 9:45 PM
Input file meeting.in Output file meeting.out

【题目描述】圆桌会议(meetingPOJ 2438

魔法师们总是为了各种问题争吵不休,这让院长很头疼,比如开圆桌会议时,两个关系不是很好的魔法师如果坐在一起可能会吵架,请问如何安排一个座次,使得相邻的两个魔法师都不会吵架?

已知一共有2n个魔法师,并且每个魔法师最多有n1个“敌人”。

【输入格式】

包含多组数据,每组数据第一行为两个整数nm1n2000mn(n1))。随后m行中每行两个整数,表示第i个魔法师和第j个魔法师的关系不是很好。输入数据中,如果已经给了第i个魔法师和第j个魔法师的关系,就不会再给第j个魔法师和第i个魔法师的关系。

两组数据间有一个空行,当nm均为0时结束全部输入。

【输出格式】

对于每组输入,如果可以安排,则在一行内输出座次序列。否则输出“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

【样例说明】

答案非唯一。