Опасные перекрестки
(Время: 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.TXT | OUTPUT.TXT |
|---|
| 1 | 6 5
3 4
2 5
6 5
1 2
4 5 | 2 5 |
Пояснение к примеру
В тесте из условия Пётр Семёнович получит следующий список: {1, 2, 1, 2, 3, 1}. Мэр Снежногорска будет считать, что перекрёстки 2 и 5 - очень опасные.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
