Operation Permutation

General Petrov loves drill practice more than anything. Once, $n$ soldiers, numbered from $1$ to $n$ for simplicity, took part in a formation. The soldiers lined up in a row, and the soldier at position $i$ had number $a_i$. Afterward, the general's adjutant walked along the line and confirmed that the order matched the one the general had chosen.

Some time later, the general wanted to arrange the soldiers in the same order again. However, he forgot how he had arranged them the first time. Fortunately, the adjutant has a good memory: for $m$ pairs of positions $x_i, y_i$, he remembers that the number of the soldier at position $x_i$ is less than the number of the soldier at position $y_i$.

The adjutant reports the pairs $x_i, y_i$ one at a time. The general wants to start arranging the soldiers quickly, though. Find the minimum $k$ such that, once the adjutant has reported the first $k$ pairs, the general can uniquely determine the desired permutation.

The first line contains two integers $n$ and $m$: the number of soldiers in the operation and the number of position pairs the adjutant remembers ($2 \le n \le 10^5$; $1 \le m \le 10^5$).

Each of the next $m$ lines contains a pair $x_i, y_i$, in the order the adjutant reports them. It means the soldier number at position $x_i$ is less than the soldier number at position $y_i$ ($1 \le x_i, y_i \le n$; $x_i \ne y_i$).

Each pair appears at most once. The input is guaranteed to be consistent: at least one permutation satisfies all the remembered conditions.

Print one integer $k$, the smallest index of a pair after which the permutation can be uniquely restored. If the permutation cannot be uniquely restored, print $-1$.

In the first example, the soldiers stood in the order $(5, 2, 1, 3, 4)$. The order can be restored already after the fourth remembered pair.

In the second example, four arrangements satisfy the input: $(1, 3, 4, 2)$, $(2, 3, 4, 1)$, $(3, 2, 4, 1)$, and $(4, 2, 3, 1)$.