G. Игра на дереве
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса и Боб играют в игру. У них есть дерево, состоящее из $$$n$$$ вершин. Изначально у Боба есть $$$k$$$ фишек, $$$i$$$-я фишка расположена в вершине $$$a_i$$$ (все эти вершины уникальны). Перед началом игры Алиса поместит фишку в одну из вершин дерева.

Игра состоит из ходов. На каждом ходу происходят следующие события (последовательно, точно в следующем порядке):

  1. Алиса либо перемещает свою фишку в соседнюю вершину, либо не перемещает ее;
  2. для каждой фишки Боба он либо перемещает ее в соседнюю вершину, либо не перемещает. Обратите внимание, что этот выбор делается независимо для каждой фишки.

Игра заканчивается, когда фишка Алисы находится в одной вершине с одной (или несколькими) фишками Боба. Обратите внимание, что фишки Боба могут находиться в одной и той же вершине, даже если они находились в разных вершинах в начале игры.

Алиса хочет максимизировать количество ходов, а Боб хочет минимизировать его. Если игра заканчивается в середине некоторого хода (Алиса перемещает свою фишку в вершину, содержащую одну или несколько фишек Боба), этот ход засчитывается.

Для каждой вершины подсчитайте, сколько ходов продлится игра, если Алиса поместит свою фишку в эту вершину.

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — количество вершин в дереве.

Затем следует $$$n - 1$$$ строка, каждая строка содержит два целых числа $$$u_i$$$, $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \ne v_i$$$) — ребра дерева. Гарантируется, что эти ребра образуют дерево.

Следующая строка содержит одно целое число $$$k$$$ ($$$1 \le k \le n - 1$$$) — количество фишек Боба.

Последняя строка содержит $$$k$$$ целых чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_k$$$ ($$$1 \le a_i \le n$$$; $$$a_i \ne a_j$$$, если $$$i \ne j$$$) — вершины, в которых изначально размещены фишки Боба.

Выходные данные

Выведите $$$n$$$ целых чисел. $$$i$$$-е из них должно быть равно числу ходов, которое продлится игра, если Алиса изначально поместит свою фишку в вершину $$$i$$$. Если одна из фишек Боба уже помещена в вершину $$$i$$$, то ответ для вершины $$$i$$$ равен $$$0$$$.

Примеры
Входные данные
5
2 4
3 1
3 4
3 5
2
4 5
Выходные данные
2 1 2 0 0
Входные данные
8
4 1
8 4
4 5
6 4
2 5
4 3
1 7
3
2 8 3
Выходные данные
3 0 0 3 1 2 3 0
Входные данные
10
2 5
4 3
7 3
7 2
5 8
3 6
8 10
7 9
7 1
4
10 6 9 1
Выходные данные
0 2 2 2 2 0 2 2 0 0