3 - スパイ (Spy) Editorial /

Time Limit: 2 sec / Memory Limit: 256 MiB

配点 : 100 点

問題文

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

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

JOI 社と IOI 社にはそれぞれ N 人の社員がいる.JOI 社の社員は j_{1}, j_{2}, \cdot \cdot \cdot , j_{N} と名付けられており,IOI 社の社員は i_{1}, i_{2}, \cdot \cdot \cdot , i_{N} と名付けられている.また,JOI 社の社員の内の一人は JOI 社の社長であり,IOI 社の社員の内の一人は IOI 社の社長である.社長を除く社員のそれぞれに対して,その社員を直接の部下とする同じ会社の社員がちょうど一人存在する.

図

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

IOI 社はいつも,JOI 社の研究プロジェクトの情報を盗むことで「途方もなく奇妙な発明」をしている.いま,JOI 社では,r_{1}, r_{2}, \cdot \cdot \cdot , r_{M} と名付けられた M 個の研究プロジェクトが発足し,IOI 社では,s_{1}, s_{2}, \cdot \cdot \cdot , s_{M} と名付けられた M 個のスパイプロジェクトが発足した.IOI 社のスパイプロジェクト s_{b} は JOI 社の研究プロジェクト r_{b} の情報を盗むプロジェクトである.

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

プロジェクト リーダー 所属する社員
研究プロジェクト 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 \leqq a \leqq N) には 2 つの整数 P_{a}, Q_{a} (0 \leqq P_{a} \leqq N かつ 0 \leqq Q_{a} \leqq 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 \leqq b \leqq M) には 2 つの整数 R_{b}, S_{b} (1 \leqq R_{b} \leqq N かつ 1 \leqq S_{b} \leqq N) が書かれており,研究プロジェクト r_{b} のリーダーが社員 j_{R_{b}} で,スパイプロジェクト s_{b} のリーダーが社員 i_{S_{b}} であることを表す.

出力

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

制約

すべての入力データは以下の条件を満たす.

  • 1 \leqq N \leqq 2\,000.
  • 1 \leqq M \leqq 500\,000.

小課題

小課題 1 [10 点]

以下の条件を満たす.

  • N \leqq 200.
  • M \leqq 200.

小課題 2 [20 点]

  • M \leqq 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} においてスパイ活動に成功する.

Source Name

JOI 2012/2013 春季トレーニング合宿 Contest Day2