棋盘大战

题目描述

童童是一个非常执着的同学，他做事情不撞南墙不回头，不达目的誓不罢休！他参加某种棋盘游戏，规则如下： 1. 两位选手轮流下棋，谁的棋子先攻击到对方司令，谁就获得胜利。 2. 选手每次下棋，不是只能移动一步，只要能移动可以一直移动，直到不能移动本次结束。 由于童童的执着，他想一次就击败对方。请你编程告诉童童一次就能击败对方的所有路线。童童的攻击棋子刚开始位于1号位置。

输入格式

第一行两个整数 $n$ 和 $e$，分别表示落棋点数量，落棋点之间边的数量。$n$ 个落棋点编号从 $1\sim n$。 接下来有 $e$ 行，每行 $2$ 个整数 $a$ 和 $b$，表示一条边两端的落棋点编号。 最后一行一个整数 $Q$，表示敌方司令编号。

输出格式

先输出若干行，每行一条从起点1到敌方司令Q的路线。（优先向编号小的位置移动） 最后一行一个整数，表示路线总数。

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

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

提示

#### 数据范围与提示 $4≤n≤10，1

来源

童程童美