Toposort

Accepts: 30
Submissions: 98
Time Limit: 10000/5000 MS (Java/Others)
Memory Limit: 131072/131072 K (Java/Others)
Problem Description
There is a directed acyclic graph with $n$ vertices and $m$ edges. You are allowed to delete exact $k$ edges in such way that the lexicographically minimal topological sort of the graph is minimum possible.
Input
There are multiple test cases. The first line of input contains an integer $T$ indicating the number of test cases. For each test case: The first line contains three integers $n$, $m$ and $k$ $(1 \le n \le 100000, 0 \le k \le m \le 200000)$ -- the number of vertices, the number of edges and the number of edges to delete. For the next $m$ lines, each line contains two integers $u_i$ and $v_i$, which means there is a directed edge from $u_i$ to $v_i$ $(1 \le u_i, v_i \le n)$. You can assume the graph is always a dag. The sum of values of $n$ in all test cases doesn't exceed $10^6$. The sum of values of $m$ in all test cases doesn't exceed $2 \times 10^6$.
Output
For each test case, output an integer $S = (\displaystyle\sum_{i=1}^{n}{i\cdot p_i}) \text{ mod } (10^9 + 7)$, where $p_{1}, p_{2}, ..., p_{n}$ is the lexicographically minimal topological sort of the graph.
Sample Input
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
Sample Output
30
27
30