Задачи
Туристическое агенство
Туристическое агенство
Антон работает в межгалактическом туристическом агентстве. Довольно часто ему приходится прокладывать путь с одной планеты на другую с использованием существующих рейсов космических кораблей. К сожалению, количество рейсов невелико, поэтому пассажирам часто приходится пересаживаться на промежуточных планетах.
Антон заметил, что некоторые планеты используются в качестве промежуточных чаще, чем другие. Он решил провести исследование -- для каждой планеты \textbf{A} он хотел бы узнать, сколько существует пар различных планет \textbf{(B, C)}, таких что любой путь с планеты \textbf{B} на планету \textbf{C} проходит через планету \textbf{A}.
Помогите Антону!
\InputFile
Первая строка входного файла содержит два целых числа: \textbf{N} и \textbf{M} -- количество планет и количество рейсов космических кораблей, соответственно (\textbf{2} ≤ \textbf{N} ≤ \textbf{20000}, \textbf{1} ≤ \textbf{M} ≤ \textbf{200000}). Следующие \textbf{M} строк описывают рейсы космических кораблей. Каждый рейс связывает две планеты, и им можно воспользоваться в любом из двух направлений. С любой планеты можно добраться до любой другой.
\OutputFile
В выходной файл выведите \textbf{N} целых чисел -- для каждой планеты \textbf{A} выведите количество пар различных планет, таких что любой путь с одной планеты на другую проходит через \textbf{A}.
Входные данные #1
7 9 1 2 1 3 1 4 1 5 1 6 1 7 2 3 4 5 6 7
Выходные данные #1
18 6 6 6 6 6 6