Chu trình đơn ngắn nhất
Points
45
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Đề 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$
Community Discussion