Kiểm tra đồ thị hai phía động

General
Points
55
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Cho $N$ đỉnh ban đầu chưa có cạnh nào. Lần lượt thêm $M$ cạnh vô hướng $(u_i, v_i)$ (đánh số $1..M$). Hãy tìm chỉ số của cạnh đầu tiên làm cho đồ thị không còn là đồ thị hai phía (tức xuất hiện chu trình có độ dài lẻ). Nếu sau khi thêm tất cả $M$ cạnh đồ thị vẫn là đồ thị hai phía, in ra -1.

Dữ liệu vào
  • Dòng đầu chứa hai số nguyên $N, M$ ($1 \le N \le 10^5$, $1 \le M \le 2 \cdot 10^5$).
  • $M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u_i, v_i$ ($1 \le u_i, v_i \le N$).
Dữ liệu ra
  • Một số nguyên duy nhất là chỉ số (1-based) của cạnh đầu tiên phá vỡ tính hai phía, hoặc -1.
Ví dụ
Input Output
4 4
1 2
2 3
3 4
1 3
4
4 4
1 2
2 3
3 4
4 1
-1
Giới hạn
  • $1 \le N \le 10^5$, $1 \le M \le 2 \cdot 10^5$
Draft saved