题目描述

题目译自 JOISC 2013 Day2 T3 「スパイ」

你听说过 Just Odd Inventions 公司吗？这家公司的业务是进行「只是有点奇特的发明」（just odd inventions），我们简称它为 JOI 公司。

另外，你知道 Incredibly Odd Inventions 公司吗？这家公司的业务是进行「极其奇特的发明」（incredibly odd inventions），我们简称它为 IOI 公司。

JOI 公司和 IOI 公司各有 $N$ 名员工。JOI 公司的员工分别命名为 $j_{1}, j_{2}, \cdots, j_{N}$，IOI 公司的员工分别命名为 $i_{1}, i_{2}, \cdots, i_{N}$。两家公司各有一名员工是公司的总裁，除总裁外，每名员工都有且仅有一名直接上司（来自同公司）。

IOI 公司总是通过窃取 JOI 公司的研究项目信息来完成他们的“极其奇特的发明”。目前，JOI 公司启动了 $M$ 个研究项目，命名为 $r_{1}, r_{2}, \cdots, r_{M}$；相应地，IOI 公司也启动了 $M$ 个间谍项目，命名为 $s_{1}, s_{2}, \cdots, s_{M}$。IOI 公司的间谍项目 $s_{b}$ 专门针对 JOI 公司的研究项目 $r_{b}$ 进行信息窃取。

两家公司在项目分配员工的方式相同。每个项目指定一名领导，领导会向其所有直接下属传达命令，收到命令的员工再向自己的所有直接下属继续传达命令。以此类推，领导及其所有收到命令的员工都属于该项目，其他员工则不属于该项目。

IOI 公司的员工 $i_{a}$ 会从 JOI 公司的员工 $j_{a}$ 处窃取信息。如果 IOI 公司的员工 $i_{a}$ 属于间谍项目 $s_{b}$，且 JOI 公司的员工 $j_{a}$ 属于研究项目 $r_{b}$，则该员工在该间谍项目中成功完成间谍活动。两家公司的员工可能同时属于多个项目，IOI 公司的员工也可能在多个间谍项目中成功完成间谍活动。

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

输入格式

从标准输入中读取以下数据：

• 第一行包含两个整数 $N, M$，用空格分隔，表示 JOI 公司和 IOI 公司各有 $N$ 名员工，研究项目和间谍项目各有 $M$ 个。
• 接下来 $N$ 行中，第 $a$ $(1 \leq a \leq N)$ 行包含两个整数 $P_{a}, Q_{a}$ $(0 \leq P_{a} \leq N, 0 \leq Q_{a} \leq 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 \leq b \leq M)$ 行包含两个整数 $R_{b}, S_{b}$ $(1 \leq R_{b} \leq N, 1 \leq S_{b} \leq N)$，用空格分隔，表示研究项目 $r_{b}$ 的领导为员工 $j_{R_{b}}$，间谍项目 $s_{b}$ 的领导为员工 $i_{S_{b}}$。

输出格式

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

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

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}$ 中成功完成间谍活动。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N \leq 2000$
• $1 \leq M \leq 500000$

详细子任务附加限制及分值如下表所示。