Background

Original link: https://oier.team/problems/J3F。

Problem Description

You have $m$ triples $(u_i, v_i, w_i)$, where $1 \le u_i < v_i < w_i \le n$ is guaranteed and all triples are pairwise distinct. How many quadruples $(a, b, c, d)$ satisfy $1 \le a < b < c < d \le n$, and among these $m$ triples, there exist four triples $(a, b, c),\allowbreak (a, b, d),\allowbreak (a, c, d),\allowbreak (b, c, d)$?

Input Format

The first line contains two positive integers $n, m$, representing the value range of the triples and the number of triples.

Then follow $m$ lines, each containing a triple $u_i, v_i, w_i$, representing one triple.

Output Format

Output one line containing one non-negative integer representing the answer.

7 11
1 2 3
2 3 4
1 3 4
1 2 4
3 4 5
4 5 6
3 5 6
3 4 6
1 2 7
2 3 7
1 3 7

3

9 30
1 2 3
1 2 5
1 2 6
1 3 4
1 3 5
1 3 6
1 3 7
1 3 8
1 3 9
1 4 5
1 4 6
1 4 9
1 7 9
2 3 4
2 3 5
2 3 6
2 3 7
2 3 8
2 3 9
2 4 9
2 5 8
2 6 7
2 7 9
3 4 5
3 4 8
3 4 9
3 5 9
3 7 8
3 7 9
3 8 9

7

Hint

[Sample Explanation #1]

$(1, 2, 3, 4), (3, 4, 5, 6), (1, 2, 3, 7)$ satisfy the requirement.

[Constraints]

It is guaranteed that $4 \le n \le 3 \times 10^5$, $4 \le m \le 3 \times 10^5$.

This problem has no partial scoring.

Translated by ChatGPT 5