Trong vương quốc Eldoria, có một hiệp sĩ đang thực hiện nhiệm vụ chinh phục các pháo đài nằm trên một bản đồ hình cây với \(n\) pháo đài. Mỗi pháo đài được đánh số từ \(1\) đến \(n\), và pháo đài số \(1\) là căn cứ của hiệp sĩ.

Trong \(n\) ngày liên tiếp, hiệp sĩ có kế hoạch đến thăm các pháo đài khác nhau trên bản đồ. Mỗi ngày, hiệp sĩ sẽ đi từ căn cứ (pháo đài \(1\)) đến một pháo đài khác để chinh phục. Lộ trình đến pháo đài ngày hôm nay có thể trùng với các lộ trình mà hiệp sĩ đã đi trong các ngày trước đó. Hiệp sĩ muốn biết, trên đường đi đến pháo đài hôm nay, có bao nhiêu pháo đài mà anh ta đã từng ghé thăm trong những ngày trước.

Nhiệm vụ của bạn là giúp hiệp sĩ tính toán số pháo đài mà anh đã đi qua trên các hành trình trước khi đi đến mỗi pháo đài mới.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên \(n\) - số lượng pháo đài trong vương quốc.
• \(n - 1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\), biểu diễn con đường kết nối giữa pháo đài \(u\) và pháo đài \(v\).
• Dòng tiếp theo chứa \(n\) số nguyên \(A_i\) - danh sách các pháo đài mà hiệp sĩ sẽ thăm mỗi ngày. \(A\) là một hoán vị của các số từ \(1\) đến \(n\).

Dữ liệu ra

• In ra \(n\) số nguyên, mỗi số nguyên thứ \(i\) là số lượng pháo đài mà hiệp sĩ đã đi qua trên đường đến pháo đài \(A_i\) trong ngày thứ \(i\) mà anh đã từng ghé qua trong những ngày trước.

Ràng buộc

• \(1 \le n \le 10^5\)
• \(1 \le u,v \le n\)

Input 1

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

Output 1

0 1 0 2 1

Input 2

9
1 2
1 3
3 4
2 5
5 6
6 7
1 8
6 9
4 8 2 9 1 3 6 5 7

Output 2

0 0 0 1 0 1 2 2 4