Cho một đồ thị vô hướng đơn. Một tam giác là một tập gồm ba đỉnh phân biệt sao cho giữa mọi cặp đỉnh đều có cạnh. Thứ tự ba đỉnh không tạo ra tam giác mới.
Hãy đếm mọi tập ba đỉnh tạo thành tam giác, mỗi tập đúng một lần.
Input
Dòng đầu chứa n,m. Mỗi trong m dòng tiếp theo chứa hai đầu mút u,v của một cạnh.
Output
In một số nguyên duy nhất: số tam giác không có thứ tự của đồ thị.
Constraints
2≤n≤105.
1≤m≤2⋅105.
1≤u,v≤n và u=v.
Đồ thị không có cạnh trùng.
Scoring
Subtask 1 (50 điểm): n,m≤2000.
Subtask 2 (50 điểm): không có ràng buộc bổ sung.
Example
Test 1
Input
5 6
1 2
2 3
1 3
3 4
4 5
3 5
Output
2
Giải thích: Các bộ ba {1,2,3} và {3,4,5} có đủ ba cạnh. Không bộ ba nào khác tạo thành tam giác.
Lời giải tóm tắt
Ý tưởng: Định hướng mỗi cạnh từ đỉnh có cặp (bậc, số hiệu) nhỏ hơn sang đỉnh lớn hơn. Với từng đỉnh u, đánh dấu mọi đỉnh ở danh sách cạnh đi ra của u, rồi xét các cạnh đi ra từ từng hàng xóm v. Nếu cạnh v→w kết thúc ở một đỉnh đã đánh dấu, ba đỉnh u,v,w tạo thành một tam giác.
Chứng minh đúng: Thứ tự (bậc, số hiệu) là thứ tự toàn phần nên mỗi cạnh có đúng một hướng. Trong một tam giác, đỉnh nhỏ nhất theo thứ tự có hai cạnh đi ra, và giữa hai đỉnh còn lại có một cạnh đi từ đỉnh nhỏ hơn tới đỉnh lớn hơn. Thuật toán phát hiện đúng cấu hình này một lần và không thể phát hiện nó từ đỉnh khác.
Độ phức tạp:O(mm) theo cận định hướng bậc; bộ nhớ O(n+m).