Squirrel's Tree Home Invitation

Squirrel has just renovated his new home – a tree! The tree has \(n\) rooms and \(n-1\) branches connecting them, forming a tree structure. In other words, every two rooms are connected by a unique path. Squirrel, amazed by his living situation, invites Winnie the Pooh to visit. He provides a specific guide: Pooh must visit the rooms in the order \(a_1, a_2, \dots, a_n\). However, following this prescribed order may force Pooh to pass through some rooms repeatedly. Squirrel promises that every time Pooh enters a room, he can pick up a candy left there.

Since Pooh is fond of candies, he accepts the tour but complains about walking so much. To ensure that Pooh always has a candy while he is on his tour (except for his final arrival at the restaurant), Squirrel wants to know the minimum number of candies that must be placed in each room.

Note:

• The tree has \(n\) rooms and \(n-1\) branches connecting them. It is guaranteed that any room can be reached from any other room and that the path between any two rooms is unique.
• Pooh starts his tour at \(a_1\) and then moves from \(a_i\) to \(a_{i+1}\) along the unique simple path. When Pooh passes through (or arrives at) any room, he picks up one candy from that room.
• The last room \(a_n\) is a restaurant where a lavish feast awaits him; hence, when Pooh arrives there at the end of the tour, he does not need to pick up a candy.

Your task is to determine, for each room, the minimum number of candies that should be placed so that Pooh can pick one candy every time he enters a room (except the final arrival at \(a_n\)).

Explanation: For each segment of the journey from \(a_i\) to \(a_{i+1}\) (for \(1 \le i < n\)), consider the unique simple path between them. Pooh collects a candy at every room he enters along the path except that he already is present in \(a_i\) (so do not double count it). Also, since the final room \(a_n\) is the restaurant, the candy picked at his final arrival is not needed. Additionally, Pooh collects a candy at the very start in room \(a_1\).

Input Format: The first line contains an integer \(n\) (the number of rooms). The next \(n-1\) lines each contain two integers \(u\) and \(v\), denoting an undirected branch connecting rooms \(u\) and \(v\). The last line contains \(n\) integers representing the visiting order \(a_1, a_2, \dots, a_n\).

Output Format: Print \(n\) space‐separated integers, where the \(i\)th integer is the minimum number of candies that should be placed in room \(i\).

inputFormat

The input begins with an integer \(n\) \((1 \le n \le \text{small constraints})\), the number of rooms. The following \(n-1\) lines each contain two integers \(u\) and \(v\) denoting an edge in the tree. The last line contains \(n\) integers \(a_1, a_2, \dots, a_n\) specifying the order of the rooms that Pooh must visit.

outputFormat

Output \(n\) integers separated by spaces. The \(i\)th integer represents the minimum number of candies that must be placed in room \(i\) so that Pooh always gets a candy when entering that room (except for his final arrival at room \(a_n\)).

sample

3
1 2
2 3
1 3 2

1 1 1