Деревом называется связный граф без циклов. В корневом дереве есть особая вершина, которая называется корнем. Родитель вершины \(v\) (отличной от корня) — вершина перед \(v\) на кратчайшем пути от корня до \(v\). Дети вершины \(v\) — все вершины, для которых \(v\) является родителем.
Вам дано корневое дерево из \(n\) вершин. Вершина \(1\) — корень. Изначально все вершины здоровы.
Каждую секунду вы делаете две операции: распространение и, после этого, инъекцию:
- Распространение: для каждой вершины \(v\), если хотя бы один ребёнок \(v\) заражён, то вы можете распространить инфекцию, дополнительно заразив не более одного ребёнка \(v\) на свой выбор.
- Инъекция: вы можете выбрать одну любую здоровую вершину и заразить её.
Этот процесс повторяется каждую секунду до тех пор, пока всё дерево не будет заражено. Необходимо найти минимальное время в секундах, за которое можно заразить всё дерево.
Выходные данные
Для каждого набора входных данных выведите одно число — минимальное время в секундах, за которое можно заразить всё дерево.
Примечание
На картинке изображено дерево из первого набора входных данных в каждую секунду.
Вершина покрашена в чёрный, если она не заражена. Вершина покрашена в синий, если она заражена инъекцией в течение последней прошедшей секунды. Вершина покрашена в зелёный, если она заражена распространением в течение последней прошедшей секунды. Вершина покрашена в красный, если она заражена, но не в течение последней прошедшей секунды.
Обратите внимание, что вы можете выбирать, какие именно вершины будут заражены распространением и инъекциями.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
7
1 1 1 2 2 4
5
5 5 1 4
2
1
3
3 1
6
1 1 1 1 1
|
4
4
2
3
4
|