17748번 - Spy 서브태스크다국어

문제

あなたは Just Odd Inventions 社を知っているだろうか? この会社の業務は「ただ奇妙な発明 (just odd inventions)」をすることである.ここでは略して JOI 社と呼ぶ.

ところで,あなたは Incredibly Odd Inventions 社を知っているだろうか? この会社の業務は「途方もな く奇妙な発明 (incredibly odd inventions)」をすることである.ここでは略して IOI 社と呼ぶ.

JOI 社と IOI 社にはそれぞれ N 人の社員がいる.JOI 社の社員は j1, j2, · · · , jN と名付けられており,IOI 社の社員は i1, i2, · · · , iN と名付けられている.また,JOI 社の社員の内の一人は JOI 社の社長であり,IOI 社 の社員の内の一人は IOI 社の社長である.社長を除く社員のそれぞれに対して,その社員を直接の部下と する同じ会社の社員がちょうど一人存在する.

図 1: JOI 社と IOI 社の組織の例.社員を表す円から出る矢印はその社員の直接の部下を指している

IOI 社はいつも,JOI 社の研究プロジェクトの情報を盗むことで「途方もなく奇妙な発明」をしている.い ま,JOI 社では,r₁, r₂, · · · ,r_M と名付けられた M 個の研究プロジェクトが発足し,IOI 社では,s₁, s₂, · · · , s_M と名付けられた M 個のスパイプロジェクトが発足した.IOI 社のスパイプロジェクト s_b は JOI 社の研究プ ロジェクト r_b の情報を盗むプロジェクトである.

プロジェクトに所属する社員の決め方は JOI 社と IOI 社で同じである.1 つのプロジェクトにつき 1 人の リーダーが決められ,リーダーはその直接の部下全員に命令を下す.命令を受け取った社員はまたその直 接の部下全員に同じ命令を下す.命令を受け取った社員全てとリーダーがそのプロジェクトに所属し,そ の他の社員は所属しない

IOI 社の社員 i_a は JOI 社の社員 j_a から情報を盗む.スパイプロジェクト s_b に所属している IOI 社の社 員 i_a は, JOI 社の社員 ja が研究プロジェクト r_b に所属しているならばスパイ活動に成功する.それぞれ の会社のすべての社員は複数のプロジェクトに所属している可能性があり,IOI 社の社員は複数のスパイ プロジェクトにおいてスパイ活動に成功する可能性がある.

JOI 社と IOI 社における社員の情報とプロジェクトの情報が与えられたとき,IOI 社の社員のそれぞれに ついて,いくつのスパイプロジェクトにおいてスパイ活動に成功するかを求めるプログラムを作成せよ.

입력

標準入力から以下の入力を読み込め.

• 1 行目には整数 N, M が空白を区切りとして書かれており, JOI 社と IOI 社の社員がそれぞれ N 人で あることと,研究プロジェクトとスパイプロジェクトがそれぞれ M 個であることを表す.
• 続く N 行のうち,a 行目 (1 ≤ a ≤ N) には 2 つの整数 P_a, Q_a (0 ≤ P_a ≤ N かつ 0 ≤ Q_a ≤ N) が書かれて おり,JOI 社の社員 j_a が社員 j_Pa の直接の部下であり,IOI 社の社員 i_a が社員 i_Qa の直接の部下であ ることを表す.また,P_a = 0 のときは社員 j_a は JOI 社の社長であり,Q_a = 0 のときは社員 i_a は IOI 社の社長である.
• 続く M 行のうち,b 行目 (1 ≤ b ≤ M) には 2 つの整数 R_b, S_b (1 ≤ R_b ≤ N かつ 1 ≤ S_b ≤ N) が書かれ ており,研究プロジェクト r_b のリーダーが社員 j_Rb で,スパイプロジェクト s_b のリーダーが社員 i_Sb であることを表す.

출력

標準出力に N 行出力せよ.a 行目 (1 ≤ a ≤ N) には, IOI 社の社員 i_a がいくつのスパイプロジェクトに おいてスパイ活動に成功するかを表す 1 つの整数を出力せよ.

제한

• 1 ≤ N ≤ 2 000.
• 1 ≤ M ≤ 500 000.

서브태스크 1 (10점)

• N ≤ 200.
• M ≤ 200.

서브태스크 2 (20점)

• M ≤ 2 000 を満たす.

서브태스크 3 (70점)

追加の制限はない.

힌트