Chu trình đơn ngắn nhất

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

Cho một đơn đồ thị vô hướng gồm $N$ đỉnh và $M$ cạnh (không có khuyên, không có cạnh song song). Hãy tìm độ dài (số cạnh) của chu trình đơn có độ dài nhỏ nhất trong đồ thị.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $N, M$.

$M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ mô tả một cạnh của đồ thị.

Dữ liệu ra

In ra độ dài của chu trình ngắn nhất, hoặc -1 nếu đồ thị không có chu trình nào.

Ví dụ
Input Output
5 6
1 2
2 3
3 4
4 1
1 5
5 2
3
4 3
1 2
2 3
3 4
-1
Giới hạn
  • $1 \le N \le 2500$
  • $0 \le M \le 5000$
  • $1 \le u, v \le N$, $u \ne v$
Draft saved