P10996 [MX-J3-T3] Tuple

Original link: .

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)$?

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 one line containing a non-negative integer representing the answer.

**Sample Explanation #1** The quadruples $(1, 2, 3, 4)$, $(3, 4, 5, 6)$, and $(1, 2, 3, 7)$ satisfy the requirement. **Constraints** | Test Point ID | $n \le$ | $m \le$ | Special Property | | :-: | :-: | :-: | :-: | | $1, 2$ | $20$ | $100$ | | | $3 \sim 5$ | $80$ | $10^3$ | | | $6 \sim 8$ | $2000$ | $10^4$ | | | $9 \sim 12$ | $300$ | $5 \times 10^4$ | Triples are generated randomly and uniformly. | | $13 \sim 17$ | $300$ | $5 \times 10^4$ | | | $18$ | $2000$ | $5 \times 10^4$ | $u_i = 1$ | | $19 \sim 25$ | $2000$ | $5 \times 10^4$ | | 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