Задано корневое неориентированное дерево, состоящее из \(n\) вершин. Вершина \(1\) является корнем.
Определим массив глубин вершины \(x\), как бесконечную последовательность \([d_{x, 0}, d_{x, 1}, d_{x, 2}, \dots]\), где \(d_{x, i}\) — это количество вершин \(y\) таких, что выполняются оба следующих условия:
- \(x\) является предком \(y\);
- простой путь из \(x\) в \(y\) проходит ровно по \(i\) ребрам.
Доминирующий индекс массива глубин вершины \(x\) (или же просто доминирующий индекс вершины \(x\)) — это такой индекс \(j\), что:
- для каждого \(k < j\), \(d_{x, k} < d_{x, j}\);
- для каждого \(k > j\), \(d_{x, k} \le d_{x, j}\).
Для каждой вершины дерева вычислите ее доминирующий индекс.