- Описание
- Отправленные решения
1. Все дороги ведут в Рим
Синдбад-мореход отправился в путешествие по Италии. На его карте изображены все однонаправленные дороги между городами Италии, но нет названий, только номера городов. Между городами может быть несколько однонаправленных дорог. Известно, что все города Италии соединены с Римом, но из Рима дороги не ведут ни в один другой город Италии. Помогите Синдбаду найти номер города Рима: выведите нужное число или -1, если такого города нет.
Формат ввода
На первой строке находится количество городов в Италии ($2 \le n \le 100000$) и количество дорог ($1 \le m \le 200000$). Далее идут $m$ строк, в каждой из которых находится два числа: $a$ и $b$, которые означают наличие дороги между городом с номером $a$ и номером $b$.
Формат вывода
Выведите номер столицы Италии или выведите -1, если не нашлось города, удовлетворяющего условиям.
Ограничения
Ограничение времени
2 с
Ограничение памяти
256 МБ
Пример 1
10 9
9 5
6 5
4 5
7 5
2 5
3 5
1 5
10 5
8 5
5
Пример 2
10 9
2 9
6 9
1 9
5 9
8 9
10 9
3 9
4 9
7 9
9