问题描述
给出$n$个点$m$条边的有向无环图. 要求删掉恰好$k$条边使得字典序最小的拓扑序列尽可能小.
输入描述
输入包含多组数据. 第一行有一个整数$T$, 表示测试数据组数. 对于每组数据:
第一行包含3个整数$n$, $m$和$k$ $(1 \le n \le 100000, 0 \le k \le m \le 200000)$, 表示图中结点数目, 图中边的数目以及要删的边数.
接下来$m$行, 每行包含两个整数$u_i$ and $v_i$, 表示存在一条$u_i$到$v_i$的有向边 $(1 \le u_i, v_i \le n)$.
输入保证给定的图是一个DAG. 输入数据中$n$的和不超过$10^6$. 输入数据中$m$的和不超过$2 \cdot 10^6$.
输出描述
对于每组数据, 输出一个整数$S = (\displaystyle\sum_{i=1}^{n}{i\cdot p_i}) \text{ mod } (10^9 + 7)$, 其中$p_{1}, p_{2}, ..., p_{n}$是字典序最小的那个拓扑序列.
输入样例
3
4 2 0
1 2
1 3
4 5 1
2 1
3 1
4 1
2 3
2 4
4 4 2
1 2
2 3
3 4
1 4
输出样例
30
27
30
