#14 「 爬山 」

统计

其实 Kano 曾经到过由乃山,当然这名字一看山主就是 Yuno 嘛。当年 Kano 看见了由乃山,内心突然涌出了一股杜甫会当凌绝顶,一览众山小的豪气,于是毅然决定登山。

但是 Kano 总是习惯性乱丢垃圾,增重环卫工人的负担,Yuno 并不想让 Kano 登山,于是她果断在山上设置了结界……

Yuno 为了方便登山者,在山上造了 $N$ 个营地,编号从 $0$ 开始。当结界发动时,每当第 $i(>0)$ 号营地内有人,那么他将被传送到第 $ A_i (< i) $ 号营地,如此循环,所以显然最后只会被传送到第 $0$ 号营地。

但 Kano 并不知晓结界的情况。他登山的方法是这样的:首先分身出一个编号为 $G_i$ 的 Kano,然后将其用投石机抛掷到营地 $D_i$。Kano 总共做了 $M$ 次这样的登山操作,但每次抛出去的 Kano 都被传送回了营地 $0$,所以 Kano 只好放弃了。

但是 Kano 在思考一个问题,到底每个营地被多少只编号不同的 Kano 经过过?

输入格式

第一行两个整数 $N,M$,表示山的营地数和登山次数。

接下来 $N-1$ 行,每行一个数,第 $i$ 行为 $A_i$,表示营地 $i$ 将会传向营地 $A_i$。

接下来 $M$ 行,每行两个数 $D_i,G_i$。

输出格式

共 $N$ 行,每行表示营地 $i$ 有多少不同编号的 Kano 曾经通过。

样例数据

input

5 4
0
0
1
1
4 1
3 1
2 2
4 2

output

2
2
1
1
2

样例解释

$1$ 号 Kano 曾被抛到 $3,4$ 两个营地,传送轨迹分别是 $3-1-0,~4-1-0$

$2$ 号 Kano 曾被抛到 $2,4$ 两个营地,传送轨迹分别是 $2-0,~4-1-0$

所以 $0,1,4$ 号营地被两只 Kano 经过过,$2,3$ 号营地被一只 Kano 经过过。

数据规模与约定

$5 \leq N \leq 100000, 10 \leq M \leq 100000, max(Gi) \leq 1000000000$

时间限制:1s

空间限制:512MB

Author: NanoApe