#2725. 朋友的朋友

朋友的朋友

题目描述

李神说朋友的朋友是朋友,他来集训营专心搞社交想要尽可能多的交朋友,集训营一共有 nn 位同学,其中有mm对朋友关系,第ii个同学有一个社牛指数 Bi2Bi10B_i(2≤B_i≤10)

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

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

后面依次类推

现在李神给出一名同学的编号xx与其社牛指数BxB_x

求出 x 同学有几个朋友。

输入格式

输入共 m+2m+2

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

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

第 m+1 行输入两个整数 stst BstB_{st}

输出格式

样例

样例输入

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

样例输出

4

数据范围与提示

10n,m1000010≤n,m≤10000

1x,y,stn1≤x,y,st≤n

2Bst102≤B_{st}≤10