Вам задано дерево (неориентированный связный ацикличный граф), состоящее из \(n\) вершин. Вы играете в игру на этом дереве.
Изначально все вершины белые. На первом ходу игры Вы выбираете одну вершину и красите ее в черный. Затем на каждом ходу Вы выбираете белую вершину, смежную (соединенную ребром) с любой черной вершиной и красите ее в черный.
Каждый раз, когда вы выбираете вершину (даже во время первого хода), Вы получаете количество очков, равное размеру компоненты связности, состоящей только из белых вершин, содержащей выбранную вершину. Игра заканчивается, когда все вершины покрашены в черный цвет.
Рассмотрим следующий пример:
Вершины \(1\) и \(4\) уже покрашены в черный цвет. Если Вы выберете вершину \(2\), Вы получите \(4\) очка за компоненту связности, состоящую из вершин \(2, 3, 5\) и \(6\). Если Вы выберете вершину \(9\), Вы получите \(3\) очка за компоненту связности, состоящую из вершин \(7, 8\) и \(9\).
Ваша задача — максимизировать количество очков, которое Вы получите.
Выходные данные
Выведите одно целое число — максимальное количество очков, которое вы получите, если будете играть оптимально.