文理学院程序设计在线练习


旅行问题

Time Limit: 2 Second(s)    Memory Limit: 32 MB

Total Submission(s): 108   Accepted Submission(s): 60
Problem Description

共有n个城市,假设你从一个城市到另一个城市需要1天时间而不管路程长度,假设你在任何一座城市的停留不会耗费时间,请问d天后你恰好能到达哪些城市。当然,我们知道,城市之间要有路可通才可到达。

Input

输入数据首先包含一个整数T,表示测试实例的个数,然后是T组测试数据。
每组测试数据首先包含4个整数分别表示城市数n(城市从1到n编号,2<=n<=20),城市间直接可通的道路数m,其中1<=m<=(n-1)*n ,出发城市编号s,天数d(0<=d<=10)。
然后是m个整数数对a, b(1<=a,b<=n,且a<>b),表示a,b城市之间直接有路可通,请输出d天后你可能到达的城市编号。

Output

对于每组测试数据, 在一行上按升序输出你恰好能到达的城市编号,编号之间以1个空格分开。若d天后无法到达任何城市,输出Impossible.

Sample Input
3
3 1 2 1
1 3
3 3 1 3
1 2
1 3
2 3
3 2 1 3
1 2
1 3
Sample Output
Impossible
1 2 3
2 3
Author

flx

Source

zscas计算机知识竞赛2008/11/03