题目描述

李神说朋友的朋友是朋友，他来集训营专心搞社交想要尽可能多的交朋友，集训营一共有 $n$ 位同学，其中有$m$对朋友关系，第$i$个同学有一个社牛指数 $B_i（2≤B_i≤10）$ ，

如果社牛指数$B_i=2$，表示朋友的朋友也是朋友。

如果社牛指数$B_i=3$，表示朋友的朋友的朋友也是朋友。

后面依次类推

现在李神给出一名同学的编号$x$与其社牛指数$B_x$

求出 x 同学有几个朋友。

输入格式

输入共 $m+2$ 行

第01行两个整数 $n,m$

第02行~m+1行 每行输入两个整数 $x,y$ 表示x与y是朋友关系

第 m+1 行输入两个整数 $st$ $B_{st}$

输出格式

样例

样例输入

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

样例输出

4

数据范围与提示

$10≤n,m≤10000$

$1≤x,y,st≤n$

$2≤B_{st}≤10$