| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 11 | 7 | 6 | 75.000% |
Больше всего Генерал Петров любит строевую подготовку. Однажды в построении участвовало $n$ солдат, для простоты пронумерованных от 1ドル$ до $n$. Солдаты выстроились в ряд, при этом на месте $i$ стоял солдат с номером $a_i$. После этого адъютант генерала прошёл вдоль строя и проверил, что перестановка в точности совпадает с придуманной генералом.
Некоторое время спустя генерал захотел снова расставить солдат в том же порядке. Однако он забыл, как именно он расставил солдат в тот раз. К счастью, у адъютанта генерала хорошая память --- про $m$ пар позиций $x_i, y_i$ он помнит, что номер солдата, стоявшего на месте $x_i,ドル меньше номера солдата, стоявшего на месте $y_i$.
Адъютант стал по очереди сообщать генералу пары $x_i, y_i$. Но генерал хочет побыстрее начать строить солдат. Помогите ему определить такое минимальное $k,ドル что как только адъютант сообщит ему первые $k$ пар позиций, генерал сможет однозначно определить искомую перестановку.
В первой строке находятся два целых числа $n$ и $m$ --- количество солдат, участвовавших в операции, и количество пар позиций, которые запомнил адъютант (2ドル \le n \le 10^5$; 1ドル \le m \le 10^5$).
В следующих $m$ строках даны пары, которые помнит адъютант, в том порядке, в котором сообщает их генералу. Каждая строка содержит по два числа $x_i$ и $y_i,ドル которые означают, что номер солдата на позиции $x_i$ был меньше номера солдата на позиции $y_i$ (1ドル \le x_i, y_i \le n$; $x_i \ne y_i$).
Гарантируется, что каждая пара $x_i, y_i$ встречается во входном файле не более одного раза. Гарантируется, что входные данные корректные, то есть существует хотя бы одна перестановка, для которой выполняются все условия, которые помнит адъютант.
Выведите одно число $k$ --- минимальный номер пары позиций, после произнесения которой можно однозначно восстановить перестановку. Если входные данные таковы, что перестановку однозначно восстановить не удастся, выведите $-1$.
5 5 5 1 3 2 2 4 4 5 3 5
4
4 2 4 2 2 3
-1
В первом примере солдаты стояли в порядке $(5, 2, 1, 3, 4)$. Уже после четвёртой пары чисел, запомненной адъютантом, можно восстановить этот порядок.
Во втором примере существует четыре варианта расстановки солдат, удовлетворяющих входным данным: $(1, 3, 4, 2),ドル $(2, 3, 4, 1),ドル $(3, 2, 4, 1)$ и $(4, 2, 3, 1)$.