题目描述

给定一个有 $n$ 个结点的无向图。结点 $1$ 是消防站，结点 $k$ 是着火的街区。

请找出从结点 $1$ 到结点 $k$ 的所有简单路径。简单路径不能重复经过结点。所有路径需要按照顶点序列的字典序从小到大输出，最后再输出不同路径的总数。

输入格式

第一行输入三个正整数 $n,k,m$。接下来 $m$ 行，每行两个正整数 $a,b$，表示结点 $a,b$ 之间有一条无向道路。

输出格式

先输出所有从 $1$ 到 $k$ 的简单路径，每条路径占一行，结点编号之间用一个空格分隔。

最后一行输出一个整数，表示不同路径的总数。

数据范围与约定

$1\le k\le n\le20$，$1\le m\le n(n-1)/2$；保证从结点 $1$ 能到达结点 $k$。

可见测试数据

输入数据 1

7 5 8
1 2
1 3
2 3
2 6
3 4
4 5
5 6
6 7

输出数据 1

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

输入数据 2

9 9 12
1 2
1 3
1 9
2 3
2 7
2 9
3 4
4 5
5 6
6 7
7 8
8 9

输出数据 2

1 2 3 4 5 6 7 8 9
1 2 7 8 9
1 2 9
1 3 2 7 8 9
1 3 2 9
1 3 4 5 6 7 2 9
1 3 4 5 6 7 8 9
1 9
8

输入数据 3

2 2 1
1 2

输出数据 3

1 2
1