Phát hiện chu trình đầu tiên

Buổi 25 — Disjoint Set Union Data-structures Graphs
Points
18
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Submissions
Đề 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$
Draft saved