1458: 图的遍历

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：2 Solved：1

Description

输入一个n（n<=20）个节点的无向图以及某个节点k，按照字典序从小到大的顺序输出从节点1到节点k的所有路径，要求节点不能重复。

Input

第一行，输入目的节点k

接下来的若干行，每行2个数a和b（1<=a，b<=n，a<>b），表示无向图中的某条边。

输入结束，以0 0两个数表示。

Output

输出若干行，每行按照字典序从小到大的顺序输出从节点1到节点k的路径，每个节点之间用空格分隔。

Sample Input Copy 

6
1  2
1  3
3  4
3  5
4  6
5  6
2  3
2  4
0  0

Sample Output Copy 

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

HINT

【样例输入2】

4

2  3

3  4

5  1

1  6

7  8

8  9

2  5

5  7

3  1

1  8

4  6

6  9

0  0

【样例输出2】

1  3  2  5  7  8  9  6  4

1  3  4

1  5  2  3  4

1  5  7  8  9  6  4

1  6  4

1  6  9  8  7  5  2  3  4

1  8  7  5  2  3  4

1  8  9  6  4

Source/Category

SubmitSubmit RecordStatisticsShowOff!