병사 순열 복원

페트로프 장군은 제식 훈련을 무엇보다 좋아한다. 어느 날 $n$명의 병사가 대열에 참여했다. 편의상 병사에게는 1부터 $n$까지 번호가 매겨져 있다. 병사들은 한 줄로 섰고, $i$번째 자리에는 번호가 $a_i$인 병사가 서 있었다. 이후 장군의 부관이 줄을 따라 걸으며 배열이 장군이 정한 순서와 정확히 일치하는지 확인했다.

잠시 후 장군은 같은 순서로 병사들을 다시 세우고 싶어 했다. 그러나 처음에 어떻게 세웠는지 잊어버렸다. 다행히 부관은 기억력이 좋다. 부관은 $m$개의 위치 쌍 $x_i, y_i$에 대해, $x_i$ 자리에 있던 병사의 번호가 $y_i$ 자리에 있던 병사의 번호보다 작았다는 것을 기억한다.

부관은 쌍 $x_i, y_i$를 하나씩 장군에게 알려준다. 그러나 장군은 병사를 빨리 세우기 시작하고 싶어 한다. 부관이 처음 $k$개의 쌍을 알려준 시점에 장군이 찾는 순열을 한 가지로 정할 수 있도록, 가능한 최소의 $k$를 구하라.

첫 줄에는 두 정수 $n$과 $m$이 주어진다. $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$).

각 쌍은 최대 한 번만 나타난다. 입력은 모순이 없음이 보장된다. 기억하는 조건을 모두 만족하는 순열이 적어도 하나 존재한다.

순열을 한 가지로 복원할 수 있게 되는 가장 작은 쌍의 번호 $k$를 한 줄에 출력하라. 순열을 한 가지로 복원할 수 없다면 $-1$을 출력하라.

첫 번째 예시에서 병사들은 $(5, 2, 1, 3, 4)$ 순서로 서 있었다. 부관이 기억하는 네 번째 쌍을 알려준 뒤에는 이 순서를 복원할 수 있다.

두 번째 예시에서는 입력을 만족하는 배치가 네 가지 있다. $(1, 3, 4, 2)$, $(2, 3, 4, 1)$, $(3, 2, 4, 1)$, $(4, 2, 3, 1)$이다.