题目描述

童童小学毕业升入初中,班级共有n人,学号分别为从1~n。其中童童的学号是3号。班级n位同学在一 张关系网里,关系网有m组好友关系。 现在童童想认识学号k的同学,但他非常害羞,没办法直接介绍自己,只能通过一些中间好友的介绍。请你编写程序统计共有多少种方案。

输入格式

第一行两个整数n和m,分别表示班级人数,好友组数。(4≤n≤40) 接下来有m行,每行2个整数u和v,表示一组好友学号。(1≤u,v≤n) 最后一行一个整数k,表示小k同学学号。(1≤k≤n,且k不是3)

输出格式

一个整数,表示总方案数。

样例

输入样例 1

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

输出样例 1

4

输入样例 2

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

输出样例 2

2

输入样例 3

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

输出样例 3

10

提示

提示：好友关系是双向的，所有好友关系网可以看做一个无向图。本题就是对无向图进行遍历，在遍历过程中找到顶点3和k之间的路径数量。 图的保存可以用邻接表也可以用邻接矩阵。下面的代码示例是邻接表的例子。