Задача
В городе Лост-Хевен произошла серия загадочных преступлений. Жители напуганы и не знают, кому можно доверять. Местный Шериф позвал на помощь знаменитого детектива Нормана, чтобы тот помог ему найти главаря мафии.
Норман принялся за дело и опросил всех жителей города. В итоге он теперь знает, кто кого боится.
Норман знает, что главным подозреваемым будет тот житель города, который удовлетворяет следующим условиям:
1) Подозреваемый никого не боится.
2) Все остальные жители боятся подозреваемого.
3) Существует ровно один такой человек, который удовлетворяет первым двум условиям.
Вы - программист, который помогает Норману. Норман дал вам информацию в виде списка, кто кого боится. Помогите Норману определить главного подозреваемого.
Формат входных данных
В первой строке записано натуральное число N - количество жителей города Лост-Хевен (1 <= N <= 1000). Во второй строке содержится неотрицательное число
K (0 <= K <= 104) - количество записей сделанных Норманом после опроса всех жителей города. В следующих
K строках записано по два числа (
ai, bi) - обозначающие то, что
i-й житель
a боится жителя
b (1 <= ai, bi <= n, ai не равно bi, каждая пара (ai, bi) уникальна).
Формат выходных данных
Выведите номер подозреваемого. Если выявить подозреваемого не представляется возможным, то в ответе укажите число
-1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
1
1 2
|
2
|
|
2
|
3
2
1 3
2 3
|
3
|
|
3
|
3
3
1 3
2 3
3 1
|
-1
|
