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