财大的体育一向是十分出名的，当然体育考试也是相当难的，期末考试将近，大家都非常紧张，
但是，今年体育老师却告诉我们一个好消息，我们不考试了！
那么同学们的成绩怎么办呢？老师也想到了一个好方法：
班上有N位同学，每位同学都有唯一的学号，从1到N，
然后所有人排成一列，每位同学报出包括自己的前方所有同学的最小学号，
报的学号总和(不然排在后面的同学不就吃亏了嘛)就作为成绩判断依据，至于怎么计算成绩，就是体育老师的事了。
不过有的同学和某个同学之间有矛盾或者害羞(女(男)神？⁄(⁄ ⁄•⁄ω⁄•⁄ ⁄)⁄)，他不希望那个人排在他前面。
大家都想要获得最好的成绩，所以你需要组织一下大家，排出一个满足大家要求而且总分最大的队伍，排好后把大家报的学号总和上报给体育老师就好了。
第一行为一个整数T，表示有T(1≤T≤30) 组数据。(如果需要，必须使用long long和%lld)
每组数据，第一行输入两个整数N和M(1≤N≤50000,0≤M≤50000)，分别表示班级人数和某些同学的特殊要求。
接下来M行，每行两个整数A 和B(1≤A,B≤N)，表示学号为A的同学不希望学号为B的同学排在他之前。
题目保证至少有一种排列符合要求。
对于每组数据，输出最大分数(就是每个同学报的学号的总和)。
3
1 0
2 1
1 2
3 1
3 11
2
6