Phát hiện chu trình đầu tiên
Points
18
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Đề bài
Cho đồ thị gồm $N$ đỉnh (đánh số $1..N$) và $Q$ cạnh vô hướng được thêm vào lần lượt theo thứ tự từ $1$ đến $Q$. Hãy tìm chỉ số của cạnh đầu tiên (theo thứ tự từ $1$) khi thêm vào sẽ tạo thành chu trình trong đồ thị. Nếu sau khi thêm tất cả $Q$ cạnh mà đồ thị vẫn không có chu trình, in ra -1.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N, Q$ ($1 \le N, Q \le 10^5$).
- $Q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ ($1 \le u, v \le N$).
Dữ liệu ra
- Một số nguyên duy nhất là kết quả bài toán.
Ví dụ
| Input | Output |
|---|---|
| 4 4 1 2 2 3 3 1 3 4 |
3 |
Giới hạn
- $1 \le N, Q \le 10^5$
Community Discussion