Kết quả trận đấu robot rap

Có $n$ robot thi đấu rap. Mỗi robot có một mức kỹ năng riêng biệt (không hai robot nào bằng nhau). Robot $i$ thắng robot $j$ khi và chỉ khi robot $i$ có kỹ năng cao hơn robot $j$, và quan hệ thắng có tính bắc cầu.

Có $m$ trận đấu diễn ra lần lượt theo thứ tự. Trận thứ $i$ cho biết robot $u_i$ thắng robot $v_i$.

Hãy tìm số nguyên $k$ nhỏ nhất sao cho chỉ với kết quả của $k$ trận đầu tiên, thứ tự xếp hạng của tất cả robot theo mức kỹ năng đã được xác định duy nhất. Nếu ngay cả khi biết kết quả của cả $m$ trận mà vẫn còn nhiều hơn một cách xếp hạng thỏa mãn, in ra $-1$.

Dữ liệu đảm bảo tồn tại ít nhất một cách xếp hạng thỏa mãn toàn bộ $m$ trận đã cho.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$: số robot và số trận đấu.
• $m$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $u_i$ và $v_i$ cho biết trong trận thứ $i$ robot $u_i$ thắng robot $v_i$.

Dữ liệu ra

• In ra số $k$ nhỏ nhất sao cho $k$ trận đầu tiên đã xác định duy nhất thứ tự xếp hạng, hoặc $-1$ nếu cả $m$ trận vẫn không đủ.

Ràng buộc

• $2\le n\le {10}^5$
• $1\le m\le min({\displaystyle \frac{n(n-1)}{2}},{10}^5)$
• $1\le u_i,v_i\le n$, $u_i\ne v_i$
• Không có hai trận nào cùng một cặp robot.

Ví dụ