题目描述(ID:12283)
标题: 乘胜追击
标签: 搜索 图的遍历
详情:
小明到了室内,Ferrari却不见了踪影,地上有张纸条,上面写着:“挺聪明的嘛,小鬼!但是这次你永远也找不到我了!除了入点你可以经过两次以外,你只要走了重复的路或经过重复的点,你就永远从这个世界消失了!敢来找我吗?哈哈哈!”小明不知所措,这里十分复杂,但是小明已经得到了一幅地图,是所有的路有路(第一个室是入点),请求他是否能经过所有的室,并回到入点(一定保证他的安全)。
输入格式:
输入文件cszj.in共m+1行。第一行输入n,m,表示有n个点(包括起点)和m条边。
以下m行每行两个数,表示这两个点有边相连。
输出格式:
输出文件cszj.out共1行或2行。如果能完成任务则输出两行,第一行输出“OK!”,第二行输出经过的点(多种方案只需输出最小的一种);如果不能完成任务则输出一行,输出“Impossible!”。
限制: 50%的数据满足:1<=n <=5
100%的数据满足:1<=n <=10, 1<=m <=30
样例:

输入

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

输出

OK!
1 2 3 4 5 1

输入

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

输出

Impossible!
登录并解答