Một đồ thị được gọi là hai phía khi có thể chia tập đỉnh thành hai phần sao cho không có cạnh nào nối hai đỉnh thuộc cùng một phần.

Trong bài toán này, ~m~ cạnh sẽ lần lượt được thêm vào một đồ thị rỗng (đồ thị không có cạnh) gồm ~n~ đỉnh.

Yêu cầu: Hãy xác định chỉ số của cạnh đầu tiên mà sau khi thêm cạnh đó vào, đồ thị không còn giữ được tính hai phía nữa.

Input

• Dòng đầu tiên gồm hai số nguyên ~n~ mà ~m~ ~(1 \le n, m \le 3 \cdot 10^5)~— số đỉnh ban đầu và số cạnh sẽ được thêm vào trong đồ thị.

• ~m~ dòng tiếp theo, mỗi dòng gồm 2 số nguyên ~u_i~ và ~v_i~ ~(1 \le u_i, v_i \le n)~, cho biết cạnh được thêm vào thứ ~i~ sẽ nối hai đỉnh ~u_i~ và ~v_i~. Đề bài đảm bảo đồ thị không tồn tại khuyên hoặc đa cạnh tại mọi thời điểm.

Output

• In ra một số nguyên duy nhất là chỉ số của cạnh đầu tiên (các cạnh được đánh số từ ~1~ theo thứ tự xuất hiện trong đầu vào), hoặc -1, nếu không tồn tại cạnh nào như vậy.

Scoring

Sample Input 1

4 4
1 2
2 3
1 3
2 4

Sample Output 1

3

Sample Input 2

6 4
1 2
2 3
3 4
1 4

Sample Output 2

-1

Notes

• Ở ví dụ đầu tiên, sau khi thêm cạnh thứ ~3~, đồ thị gồm các cạnh ~(1, 2)~, ~(1, 3)~ và ~(2, 3)~ không còn giữ được tính chất của đồ thị hai phía. Vậy đáp án là ~3~.

• Ở ví dụ thứ hai, sau khi thêm tất cả các cạnh, đồ thị vẫn là đồ thị hai phía.