Алиса и Боб играют в игру. У них есть дерево, состоящее из \(n\) вершин. Изначально у Боба есть \(k\) фишек, \(i\)-я фишка расположена в вершине \(a_i\) (все эти вершины уникальны). Перед началом игры Алиса поместит фишку в одну из вершин дерева.
Игра состоит из ходов. На каждом ходу происходят следующие события (последовательно, точно в следующем порядке):
- Алиса либо перемещает свою фишку в соседнюю вершину, либо не перемещает ее;
- для каждой фишки Боба он либо перемещает ее в соседнюю вершину, либо не перемещает. Обратите внимание, что этот выбор делается независимо для каждой фишки.
Игра заканчивается, когда фишка Алисы находится в одной вершине с одной (или несколькими) фишками Боба. Обратите внимание, что фишки Боба могут находиться в одной и той же вершине, даже если они находились в разных вершинах в начале игры.
Алиса хочет максимизировать количество ходов, а Боб хочет минимизировать его. Если игра заканчивается в середине некоторого хода (Алиса перемещает свою фишку в вершину, содержащую одну или несколько фишек Боба), этот ход засчитывается.
Для каждой вершины подсчитайте, сколько ходов продлится игра, если Алиса поместит свою фишку в эту вершину.
Выходные данные
Выведите \(n\) целых чисел. \(i\)-е из них должно быть равно числу ходов, которое продлится игра, если Алиса изначально поместит свою фишку в вершину \(i\). Если одна из фишек Боба уже помещена в вершину \(i\), то ответ для вершины \(i\) равен \(0\).