Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
G. Game On Tree

time limit per test

3 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputAlice and Bob are playing a game. They have a tree consisting of $$$n$$$ vertices. Initially, Bob has $$$k$$$ chips, the $$$i$$$-th chip is located in the vertex $$$a_i$$$ (all these vertices are unique). Before the game starts, Alice will place a chip into one of the vertices of the tree.

The game consists of turns. Each turn, the following events happen (sequentially, exactly in the following order):

- Alice either moves her chip to an adjacent vertex or doesn't move it;
- for each Bob's chip, he either moves it to an adjacent vertex or doesn't move it. Note that this choice is done independently for each chip.

The game ends when Alice's chip shares the same vertex with one (or multiple) of Bob's chips. Note that Bob's chips may share the same vertex, even though they are in different vertices at the beginning of the game.

Alice wants to maximize the number of turns, Bob wants to minimize it. If the game ends in the middle of some turn (Alice moves her chip to a vertex that contains one or multiple Bob's chips), this turn is counted.

For each vertex, calculate the number of turns the game will last if Alice places her chip in that vertex.

Input

The first line contains one integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of vertices in the tree.

Then $$$n - 1$$$ lines follow, each line contains two integers $$$u_i$$$, $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \ne v_i$$$) that denote the endpoints of an edge. These edges form a tree.

The next line contains one integer $$$k$$$ ($$$1 \le k \le n - 1$$$) — the number of Bob's chips.

The last line contains $$$k$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_k$$$ ($$$1 \le a_i \le n$$$; $$$a_i \ne a_j$$$ if $$$i \ne j$$$) — the vertices where the Bob's chips are initially placed.

Output

Print $$$n$$$ integers. The $$$i$$$-th of them should be equal to the number of turns the game will last if Alice initially places her chip in the vertex $$$i$$$. If one of Bob's chips is already placed in vertex $$$i$$$, then the answer for vertex $$$i$$$ is $$$0$$$.

Examples

Input

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

Output

2 1 2 0 0

Input

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

Output

3 0 0 3 1 2 3 0

Input

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

Output

0 2 2 2 2 0 2 2 0 0

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/06/2023 22:40:57 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|