P10998 [MX-J3-T3+] Tuple+

Original link: 。

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

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

**[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