认识新朋友

题目描述

童童小学毕业升入初中，班级共有 n 人，学号分别为从 1~n。其中童童的学号是 3 号。班级 n 位同学在一张关系网里，关系网有 e 组好友关系。

现在童童想认识学号 k 的同学，但他非常害羞，没办法直接介绍自己，只能通过一些中间好友的介绍。请你编写程序统计共有多少种方案。

输入格式

第一行两个整数 n 和 e，分别表示班级人数，好友组数。

接下来有 e 行，每行 2 个整数 a 和 b，表示一组好友学号。

最后一行一个整数 k，表示小 k 同学学号。

输出格式

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

样例输入 #1

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

样例输出 #1

4

数据范围

$4 \le n \le 10$，$1 \le a, b \le n$，$1 \le k \le n$，且 k 不是 3。

知识点与难度

本题涉及的知识点从属于 GESP六级（搜索基础、DFS），难度等级：⭐⭐⭐。

测试点分布