Туристическое агентство
(Время: 5 сек. Память: 32 Мб Сложность: 80%)
Антон работает в межгалактическом туристическом агентстве. Довольно часто ему приходится прокладывать путь с одной планеты на другую с использованием существующих рейсов космических кораблей. К сожалению, количество рейсов невелико, поэтому пассажирам часто приходится пересаживаться на промежуточных планетах.
Антон заметил, что некоторые планеты используются в качестве промежуточных чаще, чем другие. Он решил провести исследование – для каждой планеты A он хотел бы узнать, сколько существует пар различных планет (B,C), таких что любой путь с планеты B на планету C проходит через планету A.
Помогите Антону!
Входные данные
Первая строка входного файла INPUT.TXT содержит два целых числа: N и M – количество планет и количество рейсов космических кораблей, соответственно (2 ≤ N ≤ 20 000, 1 ≤ M ≤ 200 000). Следующие M строк описывают рейсы космических кораблей. Каждый рейс связывает две планеты, и им можно воспользоваться в любом из двух направлений. С любой планеты можно добраться до любой другой.
Выходные данные
В выходной файл OUTPUT.TXT выведите N целых чисел – для каждой планеты A выведите количество пар различных планет, таких что любой путь с одной планеты на другую проходит через A.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 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
|
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
