题目描述

你知道 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$。此外，JOI 社员工中有一人是 JOI 社的社长，IOI 社员工中有一人是 IOI 社的社长。除社长外，每位员工在各自公司内都有且仅有一名直接上司。

:::align{center}

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

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$ 的信息。

JOI 社和 IOI 社确定项目成员的方式相同。每个项目确定一名负责人，负责人向其所有直接下属下达命令。接收到命令的员工再向其所有直接下属下达相同的命令。所有接收到命令的员工以及负责人本人参与该项目，其他员工不参与。

项目	负责人	参与的员工
研究项目 $r_1$	$j_1$	$j_1, j_2, j_3$
研究项目 $r_2$	$j_2$	$j_2, j_3$
研究项目 $r_3$
研究项目 $r_4$	$j_3$

项目	负责人	参与的员工
间谍项目 $s_1$	$i_1$
间谍项目 $s_2$
间谍项目 $s_3$	$i_3$
间谍项目 $s_4$	$i_2$	$i_1, i_2, i_3$

图 2: 图 1 所示的 JOI 社与 IOI 社中项目配置示例

IOI 社员工 $i_a$ 从 JOI 社员工 $j_a$ 处窃取信息。若参与间谍项目 $s_b$ 的 IOI 社员工 $i_a$ 所对应的 JOI 社员工 $j_a$ 也参与了研究项目 $r_b$，则该次间谍活动成功。两家公司的每位员工可能参与多个项目，且 IOI 社员工可能在多个间谍项目中成功进行间谍活动。

任务

给定 JOI 社与 IOI 社的员工信息及项目信息，编写程序计算 IOI 社的每位员工在多少个间谍项目中成功完成间谍活动。

输入格式

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

• 第 $1$ 行包含两个以空格分隔的整数 $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

提示

样例 1 解释

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

• 参与间谍项目 $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 500\,000$

子任务

子任务 1 [10 分]

满足以下条件：

• $N \leq 200$
• $M \leq 200$

子任务 2 [20 分]

满足以下条件：

• $M \leq 2\,000$

子任务 3 [70 分]

无额外限制。

翻译由 DeepSeek V3 完成