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

Please read the guidelines before commenting.



  • -24
    Loc2008  commented on Dec. 27, 2023, 8:23 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.