问题描述
Soda有一个$n$个点的无向完全图, 他想要用$m$中不同的颜色给图中的边染色. 颜色标号从$1$到$m$. 一开始Soda选择了$p$条边, 然后把他们染色. 之后对于剩下来的边, 他会随机染色. 他想要知道对于所有可能的图, 有多少本质不同的好三角形.
如果$i, j, k$ $(i < j < k)$ 是图中三个点, 并且$i$和$j$之间有边, $j$和$k$之间有边, $k$和$i$之间也有边. 那么我们叫三元组$(i, j, k)$ $(i < j < k)$为一个三角形. 令边$(i,j)$, $(j,k)$, $(k,j)$的颜色分别为$x$, $y$ and $z$. 如果$x \ne y$ and $x \ne z$ and $y \ne z$, 那么这个三角形被称为一个好三角形.
两个三元组被认为不同, 当且仅当六元组$(i, j, k, x, y, z)$中至少有一个数是不同的.
输入描述
输入有多组数据. 第一行有一个整数$T$ $(1 \le T \le 100)$, 表示测试数据组数. 然后对于每组数据:
第一行包含三个整数$n$, $m$ and $p$, $(3 \le n \le 100000, 1 \le m, p \le 200000)$, 表示点的个数, 颜色数目和已经染色的边的数目.
接下来$p$行, 每行包含三个整数$u, v, c$ $(1 \le u < v \le n, 1 \le c \le m)$, 表示边$(u, v)$被染成了颜色$c$.
输入保证每条边最多只会被输入一次, 大部分数据都是小数据.
输出描述
对于每组数据, 输出本质不同的好三角形个数, 答案对$2^{32}$取模.
输入样例
1
4 6 6
1 2 1
1 3 2
1 4 3
2 3 4
2 4 5
3 4 6
输出样例
4
Hint
Huge input data, scanf is recommended.
