작전 <<순열>>

페트로프 장군은 열병식을 가장 좋아한다. 어느 날 열병식에 $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, 2, 1, 3, 4)$ 순서로 서 있었다. 부관이 기억한 네 번째 수 쌍이 나온 뒤에 이미 이 순서를 복원할 수 있다.

두 번째 예제에서 입력 데이터를 만족하는 병사 배치는 $(1, 3, 4, 2)$, $(2, 3, 4, 1)$, $(3, 2, 4, 1)$, $(4, 2, 3, 1)$ 네 가지가 있다.