程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> 更多編程語言 >> 編程解疑 >> as-孩子的晚餐問題

as-孩子的晚餐問題

編輯:編程解疑
孩子的晚餐問題

Description

Usually children in kindergarten like to quarrel with each other. This situation annoys the child-care women. For instant, when diner time comes, a fierce conflict may break out when a certain couple of children sitting side by side who are hostile with each other. Although there aren't too many children dining at the same round table, but the relationship of "enemy" or "friend" may be very complex. The child-care women do come across a big problem. Now it is time for you to help them to figure out a proper arrangement of sitting, with which no two "enemy" children is adjacent.

Now we assume that there are 2 * n children who sit around a big table, and that none has more than n - 1 "enemies".
Input

The input is consisted of several test blocks. For each block, the first line contains two integers n and m (1 <= n <= 200, 0 <= m <= n (n - 1)). We use positive integers from 1 to 2 * n to label the children dining round table. Then m lines followed. Each contains positive integers i and j ( i is not equal to j, 1 <= i, j <= 2 * n), which indicate that child i and child j consider each other as "enemy". In a input block, a same relationship isn't given more than once, which means that if "i j" has been given, "j i" will not be given.

There will be a blank line between input blocks. And m = n = 0 indicates the end of input and this case shouldn't be processed.
Output

For each test block, if the proper arrangement exist, you should print a line with a proper one; otherwise, print a line with "No solution!".
Sample Input

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
Sample Output

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

最佳回答:


http://blog.csdn.net/liuke19950717/article/details/51290445

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved