Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Опасные перекрестки

(Время: 2 сек. Память: 16 Мб Сложность: 22%)

Мэр города Снежногорск хочет сделать самые безопасные дороги в мире, для этого сначала он хочет понять, как обстоят дела с перекрестками и исправить самые опасные. Он попросил начальника строительной бригады Петра Семеновича провести обследование дорог и сообщить опасность каждого перекрестка.

Опасность каждого перекрестка определяется индексом опасности, который равен количеству пересекающихся дорог на перекрестке. Чем больше дорог пересекается на перекрестке, тем он опаснее. Все перекрестки пронумерованы от 1 до N.

Петр Семенович должен выписать все индексы опасности в упорядоченный список по номерам перекрестков и отправить его мэру. Так как мэр не очень хорошо разбирается в градоустройстве, он будет думать, что перекресток очень опасен, если индекс его опасности больше индекса опасности соседних по списку перекрестков. Если соседних перекрестков нет, то перекресток считается опасным. Ваша задача по карте дорог города определить какие перекрестки мэр посчитает очень опасными. Если таких перекрёстков нет, выведите -1.

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

Первая строка входного файла INPUT.TXT содержит целые числа N и M - количество перекрестков и количество дорог соответственно (1 ≤ N ≤ 2×104, 0 ≤ M ≤ 2×105). Следующие M строк содержат два числа U и V - номера перекрестков между которыми есть дорога (1 ≤ U, V ≤ N).

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

В выходной файл OUTPUT.TXT выведите через пробел номера всех перекрестков в упорядоченном по возрастанию порядке, которые мэр посчитает очень опасными.

Пример

INPUT.TXTOUTPUT.TXT
16 5
3 4
2 5
6 5
1 2
4 5
2 5

Пояснение к примеру

В тесте из условия Пётр Семёнович получит следующий список: {1, 2, 1, 2, 3, 1}. Мэр Снежногорска будет считать, что перекрёстки 2 и 5 - очень опасные.


Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2005 / 2006
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014 7-8 классы
 2013 / 2014 9-11 классы
 2014 / 2015 7-8 классы
 2014 / 2015 9-11 классы
 2015 / 2016 7-8 классы
 2015 / 2016 9-11 классы
 2016 / 2017 7-8 классы
 2016 / 2017 9-11 классы
 2017 / 2018 7-8 классы
 2017 / 2018 9-11 классы
 2018 / 2019 7-8 классы
 2018 / 2019 9-11 классы
 2019 / 2020 7-8 классы
 2019 / 2020 9-11 классы
 A. Ограда
 B. Опасные перекрестки
 C. Странная Лотерея
 D. Пароль
 E. Зоопарк Глеба

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru