问题描述

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

输入

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

输出

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

Samples

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

4

Limitation

1s, 1024KiB for each test case.