2013年7月23日 星期二

10982 - Troublemakers

每個學校班級中,總是會有那群搗蛋鬼,使得老師的生活苦不堪言。對老師來說,搗蛋鬼還算可以控制的,如果將成對的搗蛋鬼放在同一班,上課就會變得十分困難。現在有 n 個搗蛋鬼,而其中會有 m 對搗蛋鬼會造成老師上課的為害,老師決定將其拆成兩班上課,使得麻煩的事件減少一半。

寫一個程式找到分配方法,符合老師的要求。

Input
輸入第一行會有一個整數 N,表示皆下來有多少測資組。

對於每組測資第一行有兩個整數 n, m (0 <= n <= 100, 0 < m < 5000)。
接下來會有 m 行,每行上有一對整數 u, v 表示這兩個小孩在同一般即會鬧事。

搗蛋鬼的編號為 1 到 n

Output
對於每組測資,先輸出  "Case #x:" 測資組編號,以及一個整數 L,表示其中一個班級的人數,下一行以空白隔開輸出該班級的每個搗蛋鬼的編號。

如果沒有辦法符合老師的條件,則輸出 "Impossible." 取代 L 的位置以及一行空行

Sample Input Sample Output
2
4 3
1 2
2 3
3 4
4 6
1 2
1 3
1 4
2 3
2 4
3 4
Case #1: 3
1 3 4
Case #2: 2
1 2