속도 줄이기

농부 John에게는 $1 \dots N$번으로 번호가 매겨진 소 $N$마리가 있습니다. 매일 각 소는 외양간에서 자신만의 목초지로 걸어갑니다.

목초지들은 $N$개의 노드로 이루어진 트리를 이루며, 외양간은 $1$번 목초지에 있습니다. 정확히 $N-1$개의 양방향 길이 목초지들을 연결하고, 직접 연결된 두 목초지 사이에는 길이 정확히 하나 있으므로 임의의 두 목초지 사이의 경로는 유일합니다. $i$번째 길은 목초지 $A_i$와 $B_i$를 연결합니다.

소 $i$는 개인 목초지 $P_i$를 소유합니다. 모든 목초지는 정확히 한 마리의 소가 소유하므로 $P_1, P_2, \dots, P_N$은 $1 \dots N$의 순열입니다.

외양간의 좁은 문으로는 한 번에 한 마리만 나갈 수 있고, 각 소는 바로 앞 소가 자신의 목초지에 도착할 때까지 기다립니다. 먼저 소 $1$이 나가 $1$번 목초지에서 $P_1$까지 걸어가 그곳에서 풀을 뜯기 시작합니다. 그다음 소 $2$가 나가 $1$번 목초지에서 $P_2$까지 걸어가고, 이런 식으로 계속됩니다.

소 $i$가 $P_i$로 걸어가는 동안, 먼저 도착한 소가 이미 자리 잡은 목초지를 지나갈 수 있습니다. 그런 목초지에 들어설 때마다 친구를 방해하지 않으려고 속도를 줄입니다. 즉, 소 $i$는 자기보다 먼저 나간 소($1 \dots i-1$번) 중에서, 그 소유 목초지가 외양간($1$번 목초지)부터 $P_i$까지의 경로 위에 있는 소의 수만큼 속도를 줄입니다.

아래 그림에서 괄호 안의 숫자는 각 목초지의 주인을 나타냅니다.

        1 (3)
       / \
  (1) 4   3 (5)
     / \
(2) 2   5 (4)

소 $1$은 $4$번 목초지로 가며 아무도 만나지 않습니다. 소 $2$는 $2$번 목초지로 가는 길에 이미 소가 있는 $4$번 목초지를 지나므로 한 번 속도를 줄입니다. 소 $3$은 $1$번 목초지(외양간)를 소유하므로 한 번도 속도를 줄이지 않습니다. 소 $4$는 $5$번 목초지로 가는 길에 이미 소가 있는 $1$번과 $4$번 목초지를 지나 두 번 속도를 줄입니다. 소 $5$는 $3$번 목초지로 가는 길에 이미 소가 있는 $1$번 목초지를 지나 한 번 속도를 줄입니다.

농부 John은 각 소가 몇 번 속도를 줄이는지 알고 싶어 합니다.

• 첫째 줄: 정수 $N$ $(1 \le N \le 100{,}000)$.
• 둘째 줄부터 $N$째 줄까지: $i+1$째 줄에 두 정수 $A_i$와 $B_i$ $(1 \le A_i, B_i \le N)$가 공백으로 구분되어 주어지며, 이는 목초지 $A_i$와 $B_i$를 잇는 길입니다.
• $N+1$째 줄부터 $N+N$째 줄까지: $N+i$째 줄에 정수 $P_i$ $(1 \le P_i \le N)$가 주어지며, 이는 소 $i$가 소유한 목초지입니다.

• 첫째 줄부터 $N$째 줄까지: $i$째 줄에 소 $i$가 $P_i$로 가는 동안 속도를 줄이는 횟수를 정수 하나로 출력합니다.