Дано корневое дерево с n вершинами. Король Ночи удаляет ровно одну вершину дерева и все ребра из этой вершины. После этого дерево распадается, и образуется лес деревьев. Вершина, которая удалена, больше не является частью дерева.
Корнем дерева в лесу деревьев является вершина в этом дереве, которая не имеет вершину-родитель. Определим силу леса, как размер самого большого дерева в лесу деревьев.
Джон Сноу хочет минимизировать силу леса дерева. Чтобы сделать это, он может выполнить следующую операцию максимум один раз.
Он удаляет ребро между вершиной и ее родителем и вставляет новое ребро между этой вершиной и любой другой вершиной в лесу, так чтобы количество деревьев в лесу оставалось таким же.
Для каждой вершины v необходимо узнать минимальное значение силы леса, сформированного удалением вершины v.
Выходные данные
Выведите n строк. i-я строка должна содержать минимальное значение силы леса, сформированного удалением i-й вершины, и применением Джоном Сноу максимум одной операции, описанной выше.