消防车 Firetruck

题意翻译

输入一个 $n$ 个结点的无向图以及某个结点 $k$，按照字典序从小到大顺序输出从结点 $1$ 到结点 $k$ 的所有路径，要求结点不能重复经过。 $n\leq20$。

题目描述

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=4&page=show_problem&problem=144 [PDF](https://uva.onlinejudge.org/external/2/p208.pdf) ![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA208/9772860d49c32b149198b217e4714e0daf523ba9.png)

输入输出格式

输入格式


![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA208/cc2dc2f62137901c79f363e045d7d9d58463c2b6.png)

输出格式


![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA208/27aa199ee9aeb614939bb7fed68dd26216098adc.png)

输入输出样例

输入样例 #1

6
1 2
1 3
3 4
3 5
4 6
5 6
2 3
2 4
0 0
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

输出样例 #1

CASE 1:
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
There are 7 routes from the firestation to streetcorner 6.
CASE 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
There are 8 routes from the firestation to streetcorner 4.