DeMen100ns và thành phố
View as PDF
Submit solution
Points:
0.50 (partial)
Time limit:
1.0s
Memory limit:
256M
Input:
stdin
Output:
stdout
Problem type
Allowed languages
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
Comments
This comment is hidden due to too much negative feedback. Show it anyway.