Задача №113324. Операция «Перестановка»
Больше всего Генерал Петров любит строевую подготовку. Однажды в построении участвовало \(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\(
).
В следующих \)
Гарантируется, что каждая пара \)
Выведите одно число \)k$ — минимальный номер пары позиций, после произнесения которой можно однозначно восстановить перестановку. Если входные данные таковы, что перестановку однозначно восстановить не удастся, выведите −1.
В первом примере солдаты стояли в порядке (5, 2, 1, 3, 4). Уже после четвёртой пары чисел, запомненной адъютантом, можно восстановить этот порядок.
Во втором примере существует четыре варианта расстановки солдат, удовлетворяющих входным данным: (1, 3, 4, 2), (2, 3, 4, 1), (3, 2, 4, 1) и (4, 2, 3, 1).