Background

Original link: https://oier.team/problems/J3D.

Problem Description

You are given $m$ triples $(u_i, v_i, w_i)$, guaranteeing that $1 \le u_i < v_i < w_i \le n$ and that 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.

The next $m$ lines each contain a triple $u_i, v_i, w_i$, representing one triple.

Output Format

Output one line containing a 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

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

Constraints

For all testdata, it is guaranteed that $4 \le n \le 2000$ and $4 \le m \le 5 \times 10^4$.

Translated by ChatGPT 5