题目背景

本题不是本次比赛的正式题目，赛时满分为 $1$ 分。

解决这道题需要使用 CCF NOI 大纲中 J 组以外的知识点。

本题和 D 题题意完全相同，仅数据范围不同。

题目描述

你有 $m$ 个三元组 $(u_i,v_i,w_i)$，保证 $1\le u_i<v_i<w_i\le n$ 且三元组两两不同。有多少组 $(a,b,c,d)$ 满足 $1\le a<b<c<d\le n$，且在这 $m$ 个三元组当中，存在四个三元组 $(a,b,c),(a,b,d),(a,c,d),(b,c,d)$？

输入格式

输入的第一行有两个正整数 $n,m$ 表示三元组数字范围和三元组个数。

之后 $m$ 行，每行一组 $u_i,v_i,w_i$ 表示一个三元组。

输出格式

输出一行一个自然数表示答案。

样例

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

样例 1 解释

有 $(1,2,3,4),(3,4,5,6),(1,2,3,7)$ 符合题意。

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

数据范围

保证 $4\le n \le 3\times 10^5$，$4\le m\le 3\times 10^5$。

本题没有部分分。