Задача №3388. Агенство путешествий
Петя работает в межгалактическом агентстве путешествий. Он часто получает запросы на поиск пути между двумя планетами по доступным межпланетным дорогам. Петя уже сделал по этому поводу целый ряд наблюдений, и сейчас его интересует следующее. Для каждой планеты \(А\) он хочет знать количество пар планет \(В\) и \(С\), таких что любой путь от планеты \(В\) к планете \(С\) проходит через планету \(А\).
Первая строка входного файла содержит два числа \(2 \leq N \leq 20000\) и \(1 \leq M \leq 200000\) – число планет и число дорог соответственно. Далее в \(M\) строках следуют описания дорог. По дорогам можно двигаться в обе стороны. Каждая дорога описывается номерами планет, которые она соединяет. Гарантируется, что от любой планеты можно добраться до любой другой.
В выходной файл выведите \(N\) чисел – для каждой планеты \(А\) выведите количество пар различных планет, таких что любой путь от одной до другой содержит \(А\).
7 9 1 2 1 3 1 4 1 5 1 6 1 7 2 3 4 5 6 7
18 6 6 6 6 6 6