3-й квалификационный раунд завершен

Задания

Показывать по одной задаче на странице / все задачи на одной странице

"E" Красивый отчёт
Ограничение по времени 5 секунд
Ограничение по памяти 256 мегабайт

Андрей занимается анализом графа подписок в одной социальной сети. Этот граф является ориентированным: если пользователь a подписан на пользователя b, то пользователь b не обязательно подписан на пользователя a.

Менеджер Андрея попросил его посчитать для каждого пользователя x, сколько существует пользователей y, таких, что от пользователя x можно добраться в графе подписок до пользователя y.

Печатать точное значение не имеет смысла, потому что оно смотрится некрасиво и моментально устареет, поэтому, вас интересует лишь примерное значение. Выполните задание менеджера и найдите эти значения с ошибкой не более чем в два раза.

Формат входных данных

В первой строке заданы целые числа n и m (1 ≤ n, m ≤ 200 000) — число пользователей социальной сети и число ситуаций, когда один пользователь подписан на другого.

Далее, в m строках идёт описание графа, i-я из этих строк содержит два целых числа ai и bi (1 ≤ ai, bi ≤ n, ai ≠ bi) и означает, что пользователь ai подписан на пользователя bi. Каждая упорядоченная пара (ai, bi) встречается во входных данных не более одного раза.

Формат выходных данных

Выведите n целых чисел qi — оценку на количество пользователей y, таких, что от пользователя i можно добраться в графе подписок до пользователя y. Если настоящее количество таких пар равно zi, должны выполняться неравенства qi ≤ 2zi и zi ≤ 2qi. Кроме того, допустимо для не более, чем 10 пользователей вывести qi, не удовлетворяющее указанным ограничениям.

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

В примере от пользователя 1 можно добраться до всех пяти пользователей. Однако, показанный ответ 7 тоже допустим, так как отличается от 5 не более, чем в два раза. Аналогично, допустимым является ответ 2 для пользователя 4.

Примеры
Входные данные
5 6
1 2
1 3
2 4
2 5
3 5
4 2
Выходные данные
7
3
2
2
1
 

Отправить решение

Загрузить Максимальный размер - 256 Кб

Вход

ВКонтакте Facebook It.Mail

Забыли пароль?

Регистрация

На вашу электронную почту была
отправлена инструкция по восстановлению пароля.