Cho đồ thị vô hướng gồm N đỉnh (đánh số từ 1) và M cạnh. Các cạnh được thêm vào lần lượt theo thứ tự. Hãy xác định cạnh đầu tiên tạo thành chu trình trong đồ thị. Nếu không có cạnh nào tạo chu trình, in ra -1.

Sử dụng DSU: khi thêm cạnh (u, v), nếu u và v đã cùng tập hợp, cạnh này tạo chu trình.

Đầu vào

• Dòng đầu chứa hai số nguyên N (1 ≤ N ≤ 10^5) và M (1 ≤ M ≤ 10^5).
• M dòng tiếp theo, mỗi dòng chứa hai số nguyên u, v (1 ≤ u, v ≤ N) — mô tả một cạnh.

Đầu ra

In ra chỉ số của cạnh (đánh số từ 1) đầu tiên tạo chu trình, hoặc -1.

Ví dụ

Input:
6 7
1 2
2 3
3 4
4 5
5 2
1 6
5 6

Output:
5