Đếm Cặp Cạnh Cắt Đứt Liên Thông
Points
55
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Đề bài
Cho một đồ thị vô hướng liên thông gồm $N$ đỉnh (đánh số từ $1$ đến $N$) và $M$ cạnh (có thể có cạnh song song nối cùng một cặp đỉnh).
Một cặp hai cạnh phân biệt ${e_1, e_2}$ ($1 \le e_1 < e_2 \le M$) được gọi là cặp cạnh cắt nếu khi đồng thời xóa bỏ cả hai cạnh $e_1$ và $e_2$ khỏi đồ thị, đồ thị trở nên không còn liên thông (tức xuất hiện ít nhất hai đỉnh không thể đi tới nhau).
Hãy đếm tổng số lượng cặp cạnh cắt của đồ thị đã cho.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N$ và $M$ ($2 \le N \le 10^5$, $N - 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, v$ ($1 \le u, v \le N$, $u \ne v$) mô tả một cạnh.
Dữ liệu ra
In ra một số nguyên duy nhất là số lượng cặp cạnh cắt.
Ví dụ
| Input | Output |
|---|---|
| 5 6 1 2 2 3 3 1 3 4 4 5 5 3 |
6 |
Giới hạn
Thời gian: 1.0s, Bộ nhớ: 256MB.
Community Discussion