e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Problems

Туристическое агенство

Туристическое агенство

Антон работает в межгалактическом туристическом агентстве. Довольно часто ему приходится прокладывать путь с одной планеты на другую с использованием существующих рейсов космических кораблей. К сожалению, количество рейсов невелико, поэтому пассажирам часто приходится пересаживаться на промежуточных планетах.

Антон заметил, что некоторые планеты используются в качестве промежуточных чаще, чем другие. Он решил провести исследование – для каждой планеты A он хотел бы узнать, сколько существует пар различных планет (B, C), таких что любой путь с планеты B на планету C проходит через планету A.

Помогите Антону!

Входные данные

Первая строка входного файла содержит два целых числа: N и M – количество планет и количество рейсов космических кораблей, соответственно (2N20000, 1M200000). Следующие M строк описывают рейсы космических кораблей. Каждый рейс связывает две планеты, и им можно воспользоваться в любом из двух направлений. С любой планеты можно добраться до любой другой.

Выходные данные

В выходной файл выведите N целых чисел – для каждой планеты A выведите количество пар различных планет, таких что любой путь с одной планеты на другую проходит через A.

Time limit 5 seconds
Memory limit 32 MiB
Input example #1
7 9
1 2
1 3
1 4
1 5
1 6
1 7
2 3
4 5
6 7
Output example #1
18
6
6
6
6
6
6