P14436 [JOISC 2013] 间谍 / Spy

你知道 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$ | $j_2$ | $j_2, j_3$ | | 研究项目 $r_4$ | $j_3$ | $j_3$ | | 项目 | 负责人 | 参与的员工 | |:-:|:-:|:-:| | 间谍项目 $s_1$ | $i_1$ | $i_1$ | | 间谍项目 $s_2$ | $i_1$ | $i_1$ | | 间谍项目 $s_3$ | $i_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$ 在多少个间谍项目中成功完成间谍活动。

### 样例 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 完成