Hàng ngày, N con bò của nông dân John đánh số từ 1 đến N lần lượt ra khỏi chuồng và đi ăn cỏ treeb cánh đồng riêng của mình. Các cánh đồng cỏ có cấu trúc như là một cây với chuồng bò ở cánh đồng 1. Có đúng N-1 con đường một chiều nối giữa các cánh đồng. Con đường thứ i nối từ cánh đồng A[i] đến cánh đồng B[i] ( 1 ≤ A[i],B[i] ≤ N).

Con bò i có cánh đồng của riêng mình mang số hiệu Pi. Cánh cửa của chuồng bò là nhỏ nên các con bò ra khỏi chuống để đi ăn cỏ theo thứ tự từ con bò 1 đến con bò thứ N. Khi con bò trước đến cánh đồng của mình rồi thì con bò tiếp theo mới ra khỏi chuồng (trước tiên con bò 1 đến cánh đồng P1, con bò 2 đến cánh đồng P2, …, )

Khi con bò i trên đường từ chuồng đến cánh đồng của mình, nếu đi qua một cánh đồng đã có con bò ăn cỏ trên đó thì nó phải đi vòng men cánh đồng để tránh đụng độ với con bò này - điều này làm cho tốc độ đến chuồng chậm lại.

Hãy tính xem với mỗi con bò, khi đến cánh đồng của mình phải đi vòng bao nhiêu lần.

Input:

• Dòng 1: chứa số nguyên dương N ( 1 ≤ N ≤ 10^5)

• N – 1 dòng tiếp theo, dòng thứ i mô tả một con đường gồm hai số A[i],B[i].

• N dòng cuối, dòng thứ j chứa số Pj

Output:

Gồm N dòng, dòng thứ i ghi số lần mà con bò i phải đi vòng trên con đường đến cánh đồng của mình.

Sample Input

5
1 4
5 4
1 3
2 4
4
2
1
5
3

Sample Output

0
1
0
2
1