스파이

당신은 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 사에서는 r1, r2, ..., rM으로 명명된 M개의 연구 프로젝트가 발족했고, IOI 사에서는 s1, s2, ..., sM으로 명명된 M개의 스파이 프로젝트가 발족했다. IOI 사의 스파이 프로젝트 sb는 JOI 사의 연구 프로젝트 rb의 정보를 훔치는 프로젝트이다.

프로젝트에 소속되는 사원을 정하는 방법은 JOI 사와 IOI 사가 같다. 프로젝트 하나당 리더 한 명이 정해지고, 리더는 자신의 직접 부하 전원에게 명령을 내린다. 명령을 받은 사원은 다시 자신의 직접 부하 전원에게 같은 명령을 내린다. 명령을 받은 사원 전원과 리더가 그 프로젝트에 소속되고, 나머지 사원은 소속되지 않는다.

그림 2: 그림 1의 JOI 사와 IOI 사에서의 프로젝트

IOI 사의 사원 ia는 JOI 사의 사원 ja로부터 정보를 훔친다. 스파이 프로젝트 sb에 소속된 IOI 사의 사원 ia는 JOI 사의 사원 ja가 연구 프로젝트 rb에 소속되어 있으면 스파이 활동에 성공한다. 각 회사의 모든 사원은 여러 프로젝트에 소속될 수 있고, IOI 사의 사원은 여러 스파이 프로젝트에서 스파이 활동에 성공할 수 있다.

JOI 사와 IOI 사의 사원 정보와 프로젝트 정보가 주어졌을 때, IOI 사의 각 사원이 몇 개의 스파이 프로젝트에서 스파이 활동에 성공하는지 구하는 프로그램을 작성하라.

표준 입력에서 다음 입력을 읽는다.

• 1번째 줄에는 정수 N, M이 공백을 구분으로 쓰여 있으며, JOI 사와 IOI 사의 사원이 각각 N명이고 연구 프로젝트와 스파이 프로젝트가 각각 M개임을 나타낸다.
• 이어지는 N개의 줄 중 a번째 줄 (1 ≤ a ≤ N)에는 두 정수 Pa, Qa (0 ≤ Pa ≤ N, 0 ≤ Qa ≤ N)가 쓰여 있으며, JOI 사의 사원 ja가 사원 jPa의 직접 부하이고 IOI 사의 사원 ia가 사원 iQa의 직접 부하임을 나타낸다. 또한 Pa = 0일 때 사원 ja는 JOI 사의 사장이고, Qa = 0일 때 사원 ia는 IOI 사의 사장이다.
• 이어지는 M개의 줄 중 b번째 줄 (1 ≤ b ≤ M)에는 두 정수 Rb, Sb (1 ≤ Rb ≤ N, 1 ≤ Sb ≤ N)가 쓰여 있으며, 연구 프로젝트 rb의 리더가 사원 jRb이고 스파이 프로젝트 sb의 리더가 사원 iSb임을 나타낸다.

표준 출력에 N개의 줄을 출력한다. a번째 줄 (1 ≤ a ≤ N)에는 IOI 사의 사원 ia가 몇 개의 스파이 프로젝트에서 스파이 활동에 성공하는지를 나타내는 정수 하나를 출력한다.

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