DeMen100ns và thành phố
Xem dạng PDF
Gửi bài giải
Điểm:
0,50 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
DeMen100ns đang có một mạng lưới giao thông với ~n~ thành phố và ~m~ con đường hai chiều. Anh ấy được giao việc phải chọn ra ~3~ thành phố phân biệt ~(i, j, k)~ sao cho:
- Tồn tại các con đường nối ~(i - j)~, ~(j - k)~ và ~(k - i)~.
Vì không biết phải chọn ra các thành phố nào, DeMen100ns muốn biết số cách anh ấy có thể chọn ra cặp ~3~ thành phố thỏa mãn điều kiện trên. Hãy giúp DeMen100ns đếm xem có bao nhiêu cách anh ấy có thể chọn.
Dữ liệu đảm bảo chỉ tồn tại nhiều nhất một con đường nối giữa hai thành phố.
Input
Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~m~ ~(2 \le n \le 10^5, 1 \le m \le 2 * 10^5)~.
~m~ dòng tiếp theo dòng thứ ~i~ chứa hai số nguyên dương ~u~, ~v~ ~(1 \le u, v \le n, u \ne v)~ — có một con đường nối giữa thành phố ~u~ và thành phố ~v~.
Output
In ra một số duy nhất là kết quả của bài toán.
Sample Input 1
4 6
1 2
1 3
1 4
2 3
2 4
3 4
Sample Output 1
4
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.