Informatica Online Judge

  간첩 [2400 / 0960]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 12   Total Tried : 11


The Champion of this Problem (C++) : gs18060 - ms / 973byte
My Best Submission (C++) : N/A

[36th 정희승(gs18103)]
Writer ID : [gs18103]

Background

옛날 옛적에 존재하던 GSHS국은 IAMCODER 정당이 장기집권을 하고 있었다. 그런데 어느 날 이 정당의 대표 안지민과 당원 이종영의 불화로 정당이 지민당과 종영당 두 개로 나뉘게 되었다. 놀랍게도 둘의 지지자 수가 같아 쪼개진 두 정당의 사람 수는 각각 n명이다. GSHS왕국은 매우 보수적인 왕국이기 때문에 모든 정당이 수직관계로 되어 있으며, 당대표 안지민과 이종영을 제외한 모든 당원에 대하여 직속상관이 정확히 한 명 존재한다. 따라서 각 정당의 직속상관과 직계부하를 이어 보면 각 정당의 인물 관계는 당대표를 루트로 하는 트리 모양으로 되어있음을 알 수 있다. 또한 각 정당에 대하여 각 당원들에게 1~n까지의 숫자를 부여하였다. 지민당의 i번 당원을 JM(i), 종영당의 i번 당원을 JY(i)라 하겠다.

그런데, 새로운 정당을 세운 종영은 점점 야심을 품기 시작하더니 결국 간첩을 보내 지민당의 기밀을 몰래 빼오려는 계획까지 세우게 되었다! 이에 종영은 지민당의 유세 활동에 자신의 당원을 몰래 침투시키려 한다. 지민당의 유세는 총 m번 진행하는데, 이 때 j번째 유세에는 지민당에서 나온 리더인 당원 JM(U(j))를 루트로 하는 서브트리에 존재하는 모든 당원들이 유세에 참가한다. 이에 종영은 각 유세에서 기밀을 빼올 간첩 팀 m개를 만들었고, j번째 리더를 JY(S(j))로 정하였다. 리더인 JY(S(j))는 자신을 루트로 하는 서브트리에 당원 JY(i)가 속하고 JM(U(j))의 서브트리에 JM(i)가 속할 때 JY(i)를 간첩으로 보낼 수 있다. 여기서 어떤 당원을 루트로 하는 서브트리란, 정당을 당대표를 루트로 하는 트리로 표현하였을 때 그 당원 및 그 당원의 모든 자식들을 포함하는 트리를 말한다.

예를 들어 다음과 같이 지민당과 종영당이 있다고 생각해보자. 총 4번의 유세를 할 것이고, 각 유세 팀 리더와 간첩 팀 리더 및 각 팀의 소속당원들은 아래 표에 주어져 있다.






이 때 첫 번째 유세에서는 종영당의 JY(1)만이 간첩 활동을 할 수 있고, 두 번째 유세에서는 아무도 간첩 활동을 할 수 없다. 세 번째 유세에서는 JY(3)만이, 네 번째 유세에서도 JY(3)만이 간첩 활동을 할 수 있다.
최종적으로는 JY(1)이 1번, JY(2)가 0번, JY(3)이 2번 간첩 활동을 할 수 있다.
종영은 이번 m번의 유세에서 모든 간첩 활동을 마쳤을 때 간첩 활동을 한 횟수에 비례하여 상을 주려고 한다. 종영이를 위해 종영당의 각 당원이 총 몇 번의 간첩 활동을 하게 되는지 구하는 프로그램을 작성해주자!

Input

첫 줄에 종영당과 지민당의 크기 n과 유세 횟수 m이 주어진다.(1<=n<=2000, 1<=m<=500000)
둘 째 줄부터 총 n개의 줄이 주어진다. 이 때 i번째 줄에 두 개의 정수 PJM(i)와 PJY(i)가 공백을 두고 주어진다.(1<=i<=n, 0<=PJM(i),PJY(u)<=n) 이 때 PJM(i)와 PJY(i)는 각각 JM(PJM(i))가 JM(i)의 직속 상관이고 JY(PJY(i))가 JY(i)의 직속상관임을 의미한다. JM(i)가 지민이(트리의 루트)일 때는 PJM(i)가 0이고, JY(i)가 종영이(트리의 루트)일 때는 PJY(i)가 0이다.
이후 m개의 줄이 주어진다. 이 때 j번째 줄에는 두 개의 정수 U(j)와 S(j)가 공백을 두고 주어진다.(1<=j<=m, 1<=U(j),S(j)<=n) 이는 j번째 유세에서 지민당의 JM(U(j))가 리더로 유세를 하고, 종영당의 JY(S(j))가 리더로 간첩 활동을 함을 의미한다.

Output

총 n개의 줄을 출력한다. k번째 줄에는 JY(k)가 총 몇 번 간첩 활동을 하는지 출력한다.

IO Example

입력 예시
3 4
0 2
1 0
2 2
1 1
2 1
2 3
3 2

출력 예시
1
0
2

설명
본문에서 설명한 경우와 같다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]