Вам дан кактус, это граф, где каждое ребро лежит не более чем на одном простом цикле.
Он дан в виде \(m\) ребер \(a_i, b_i\), вес \(i\)-го ребра равен \(i\).
Назовем путь в кактусе возрастающим если веса ребер на этом пути возрастают.
Назовем пару вершин \((u,v)\) счастливой если существует возрастающий путь, который начинается в \(u\) и кончается в \(v\).
Для каждой вершины \(u\) найдите количество других вершин \(v\), что пара \((u,v)\) счастливая.
Выходные данные
Выведите \(n\) целых чисел, необходимые значения для вершин \(1,2,\ldots,n\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
1 2
2 3
3 1
|
2 2 2
|
|
2
|
5 4
1 2
2 3
3 4
4 5
|
4 4 3 2 1
|