题目分析

有 n 名演员和 m 条“必须严格高于”关系，每条关系是“演员 a 的片酬要高于演员 b”。

• 每位演员基础片酬至少 100 元；
• 调整步长 10 元；
• 在满足所有“严格大于”关系前提下，使总片酬最小。

将演员 i 的实际片酬记为

salary[i] = 100 + 10 * level[i]

题目内容

多多制作人正在筹拍一部电影，需要招募一批演员。为了确保影片顺利拍摄，制作团队需要合理地分配每位演员的片酬，否则演员可能罢演。片酬的分配由团队成员共同商议决定，每位成员对演员的片酬标准有自己独特的评估意见。在团队讨论时，成员们可能会根据演员所饰演角色的复杂性、表演难度、台词量等因素，提出不同的薪资调整建议，例如，某些成员认为某个角色的表演难度较大，应该给予更高的片酬；而另一些成员则认为某个角色的台词较多，也应该提高该演员的报酬。团队成员的意见可以通过会议提出，并且不同成员的意见有可能存在矛盾，每条意见以一对明确的优先顺序给出，例如，某个演员的片酬应该高于另一个演员的片酬。请你帮多多计算在满足所有制作团队成员的意见下，求出一个使得演员片酬总额最小的方案。每位演员的片酬必须至少为 $100$ 元，且每次调整的增量为 $10$ 元。

输入描述

第一行为一个整数 $T(1\leq T\leq 10)$，表示共有 $T$ 个测试数据。

每组测试数据:

第一行为两个整数 $n(1\leq n\leq 10000)$ 和 $m(1\leq m\leq 20000)$，分别表示招募演员的总数和制作团队成员提出的意见数。

接下来的 $m$ 行:

每行输入两个整数 $a_i,b_i(1\leq a_i,b_i \leq n)$ 表示有制作团队成员认为演员 $a_i$ 的片酬应当比演员 $b_i$ 的片酬高。

输出描述

每组数据输出一个结果，每个结果占一行，如果满足不了所有制作团队成员的意见则输出 $-1$。

补充说明

对于 $20$% 的数据有: $1\leq n\leq 100,1\leq m\leq 200$

对于 $40$% 的数据有: $1\leq n\leq 1000,1\leq m\leq 2000$

对于 $100$% 的数据有: $1\leq n\leq 10000,1\leq m\leq 20000$

示例1

输入

1
7 4
7 2
4 6
2 5
7 5

输出

740

说明

演员 $7$ 片酬需要比 $2,5$ 高

演员 $4$ 片酬需要比 $6$ 高

演员 $2$ 片酬需要比 $5$ 高

因此总额最小的招募方案为:

|演员|演员$1$|演员$2$|演员$3$|演员$4$|演员$5$|演员$6$|演员$7$|

|片酬|$100$|$110$|$100$|$110$|$100$|$100$|$120$|

总计片酬 $740$

示例2

输入

1
3 2
1 3
3 2

输出

330

说明

演员 $1$ 片酬需要比 $3$ 高

演员 $3$ 片酬需要比 $2$ 高

因此总额最小的招募方案为:

|演员|演员$1$|演员$2$|演员$3$|

|片酬|$120$|$100$|$110$|

总计片酬 $330$