你知道 Just Odd Inventions 公司吗？这家公司的业务是进行“仅仅是奇妙的发明 (just odd inventions)”。在这里简称为 JOI 公司。

顺便问一下，你知道 Incredibly Odd Inventions 公司吗？这家公司的业务是进行“极其奇妙的发明 (incredibly odd inventions)”。在这里简称为 IOI 公司。

JOI 公司和 IOI 公司各有 $N$ 名员工。JOI 公司的员工被命名为 $j_1, j_2, \dots, j_N$，IOI 公司的员工被命名为 $i_1, i_2, \dots, i_N$。此外，JOI 公司的一名员工是 JOI 公司的社长，IOI 公司的一名员工是 IOI 公司的社长。对于除社长以外的每一名员工，在同一公司内恰好有一名员工是该员工的直接上司。

图 1: JOI 公司和 IOI 公司的组织结构示例。从代表员工的圆圈出发的箭头指向该员工的直接下属。

IOI 公司总是通过窃取 JOI 公司研究项目的信息来进行“极其奇妙的发明”。现在，JOI 公司启动了 $M$ 个研究项目，命名为 $r_1, r_2, \dots, r_M$，IOI 公司启动了 $M$ 个间谍项目，命名为 $s_1, s_2, \dots, s_M$。IOI 公司的间谍项目 $s_b$ 是窃取 JOI 公司研究项目 $r_b$ 信息的项目。

JOI 公司和 IOI 公司确定项目所属员工的方式相同。每个项目指定一名领导者，领导者向其所有直接下属下达命令。收到命令的员工也会向其所有直接下属下达相同的命令。所有收到命令的员工以及领导者都属于该项目，其他员工则不属于该项目。

图 2: 图 1 中 JOI 公司和 IOI 公司的项目示例

IOI 公司的员工 $i_a$ 从 JOI 公司的员工 $j_a$ 那里窃取信息。如果 IOI 公司的员工 $i_a$ 属于间谍项目 $s_b$，且 JOI 公司的员工 $j_a$ 属于研究项目 $r_b$，则间谍活动成功。每家公司的所有员工都可能属于多个项目，IOI 公司的员工也可能在多个间谍项目中成功进行间谍活动。

题目描述

给定 JOI 公司和 IOI 公司的员工信息以及项目信息，请编写一个程序，计算 IOI 公司的每一名员工在多少个间谍项目中成功进行了间谍活动。

输入格式

从标准输入读取以下内容：

• 第 1 行包含两个整数 $N, M$，以空格分隔，表示 JOI 公司和 IOI 公司各有 $N$ 名员工，研究项目和间谍项目各有 $M$ 个。
• 接下来的 $N$ 行中，第 $a$ 行 ($1 \le a \le N$) 包含两个整数 $P_a, Q_a$ ($0 \le P_a \le N$ 且 $0 \le Q_a \le N$)，表示 JOI 公司的员工 $j_a$ 是员工 $j_{P_a}$ 的直接下属，IOI 公司的员工 $i_a$ 是员工 $i_{Q_a}$ 的直接下属。此外，当 $P_a = 0$ 时，员工 $j_a$ 是 JOI 公司的社长；当 $Q_a = 0$ 时，员工 $i_a$ 是 IOI 公司的社长。
• 接下来的 $M$ 行中，第 $b$ 行 ($1 \le b \le M$) 包含两个整数 $R_b, S_b$ ($1 \le R_b \le N$ 且 $1 \le S_b \le N$)，表示研究项目 $r_b$ 的领导者是员工 $j_{R_b}$，间谍项目 $s_b$ 的领导者是员工 $i_{S_b}$。

输出格式

输出 $N$ 行到标准输出。第 $a$ 行 ($1 \le a \le N$) 输出一个整数，表示 IOI 公司的员工 $i_a$ 在多少个间谍项目中成功进行了间谍活动。

数据范围

所有输入数据满足以下条件：

• $1 \le N \le 2\,000$
• $1 \le M \le 500\,000$

子任务

子任务 1 [10 分] 满足以下条件： $N \le 200$ $M \le 200$

子任务 2 [20 分] * 满足 $M \le 2\,000$

子任务 3 [70 分] 无附加限制。

样例

输入样例 1

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

输出样例 1

1
0
2

说明

此输入输出对应题目中的示例。此时：

• 属于间谍项目 $s_1, s_2, s_4$ 的员工 $i_1$，由于员工 $j_1$ 属于研究项目 $r_1$，因此在间谍项目 $s_1$ 中间谍活动成功。
• 属于间谍项目 $s_4$ 的员工 $i_2$，由于员工 $j_2$ 不属于研究项目 $r_4$，因此在任何间谍项目中均未成功。
• 属于间谍项目 $s_3, s_4$ 的员工 $i_3$，由于员工 $j_3$ 属于研究项目 $r_3, r_4$，因此在间谍项目 $s_3, s_4$ 中间谍活动成功。