스파이 Batch 컴파일 명령

당신은 Just Odd Inventions 사를 알고 있나요? 이 회사의 업무는 "그냥 이상한 발명(just odd inventions)"를 하는 것입니다. 이 문제에서는 편의상 JOI 사라고 부르겠습니다.

그런데, 당신은 Incredibly Odd Inventions 사를 알고 있나요? 이 회사의 업무는 "믿을 수 없을 정도로 이상한 발명(incredibly odd inventions)"를 하는 것입니다. 이 문제에서는 편의상 IOI 사라고 부르겠습니다.

JOI 사와 IOI 사에는 각각 N명의 사원이 있습니다. JOI 사의 사원은 각각 j₁, j₂, ..., j_N 중 하나로 불리며, IOI 사의 사원은 각각 i₁, i₂, ..., i_N 중 하나로 불립니다. 또한, JOI 사의 사원 중 한 명은 JOI 사의 사장이며, IOI 사의 사원 중 한 명은 IOI 사의 사장입니다. 두 회사 모두, 사장을 제외한 각 사원에 대해, 그 사원을 직계 부하로 삼은 사원이 정확히 한 명 존재합니다.

[그림 1] JOI 사와 IOI 사의 조직의 예. 원은 사원을 나타냅니다. 사원에서 나오는 화살표는, 그 사원의 직계 부하를 가리킵니다.

IOI 사는 언제나 JOI 사의 정보를 몰래 빼내어, "믿을 수 없을 만큼 이상한 발명(incredibly odd inventions)"을 하고 있습니다. 지금 JOI 사에서는, r₁, r₂, ..., r_M으로 명명된 M개의 연구 팀을 결성했습니다. IOI 사는 이에 따라, s₁, s₂, ..., s_M으로 명명된 M개의 스파이 팀을 결성했습니다. IOI 사의 스파이 팀 s_b는 JOI 사의 연구 팀 r_b의 정보를 빼내야 합니다.

두 회사 모두 각 팀에 소속될 사원을 결정하는 방식은 같습니다. 각 팀마다 한 사람의 리더가 결정됩니다. 먼저, 리더는 자신의 직계 부하들에게 명령을 내립니다. 이후, 명령을 받은 사원들은 자신의 직계 부하들에게 명령을 내립니다. 명령을 받은 모든 사원들과 리더는 해당 팀에 소속되고, 명령을 받지 않은 리더가 아닌 모든 사원들은 해당 팀에 소속되지 않습니다.

[그림 2] 그림 1의 JOI 사와 IOI 사에서 결성된 팀의 예

IOI 사의 사원 i_a는 JOI 사의 사원 j_a로부터 정보를 빼냅니다. 스파이 팀 s_b에 소속된 IOI 사의 사원 i_a는, JOI 사의 사원 j_a가 연구 팀 r_b에 소속되어 있다면, 스파이 활동에 성공합니다. 두 회사의 모든 사원은 여러 개의 팀에 소속되어 있을 가능성이 있고, IOI 사의 사원은 여러 개의 스파이 팀에서 스파이 활동에 성공할 가능성이 있습니다.

해야 할 일

JOI 사와 IOI 사의 사원의 정보와 팀에 대한 정보가 주어졌을 때, IOI 사의 각 사원에 대해, 이 사원이 몇 개의 스파이 팀에서 스파이 활동에 성공할지를 구하는 프로그램을 작성하세요.

입력 형식

• 첫 번째 줄에 두 개의 정수 N과 M이 주어집니다. 이는 IOI 사와 JOI 사의 사원이 각각 N명이며, 연구 팀과 스파이 팀이 각각 M개임을 나타냅니다.
• 이후 N개의 줄이 주어집니다. 이 중 a번째 (1 ≤ a ≤ N) 줄에는 두 개의 정수 P_a, Q_a가 주어집니다. 이는 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) 줄에는 두 개의 정수 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 ≤ N ≤ 2 000.
• 1 ≤ M ≤ 500 000.

부분문제

부분문제 1 (10점)

• 1 ≤ N ≤ 200.
• 1 ≤ M ≤ 200.

부분문제 2 (20점)

• 1 ≤ M ≤ 2 000.

부분문제 3 (70점)

추가 제약 조건이 없습니다.

예제

이 예제는 위 그림과 같습니다. 이 때,

• 스파이 팀 s₁, s₂, s₄에 속하는 사원 i₁은, 사원 j₁이 연구 팀 r₁에 속하기 때문에, 스파이 팀 s₁에서 스파이 활동에 성공합니다.
• 스파이 팀 s₄에 속하는 사원 i₂는, 사원 j₂가 연구 팀 r₄에 속하지 않기 때문에, 스파이 활동에 실패합니다.
• 스파이 팀 s₃, s₄에 속하는 사원 i₃는, 사원 j₃이 연구 팀 r₃, r₄에 속하기 때문에, 스파이 팀 s₃, s₄에서 스파이 활동에 성공합니다.