Gym Class

众所周知，度度熊喜欢各类体育活动。

今天，它终于当上了梦寐以求的体育课老师。第一次课上，它发现一个有趣的事情。在上课之前，所有同学要排成一列， 假设最开始每个人有一个唯一的ID，从1到NN，在排好队之后，每个同学会找出包括自己在内的前方所有同学的最小ID，作为自己评价这堂课的分数。麻烦的是，有一些同学不希望某个（些）同学排在他（她）前面，在满足这个前提的情况下，新晋体育课老师——度度熊，希望最后的排队结果可以使得所有同学的评价分数和最大。

Input

第一行一个整数TT，表示T(1≤T≤30)T(1≤T≤30) 组数据。

对于每组数据，第一行输入两个整数NN和M(1≤N≤100000,0≤M≤100000)M(1≤N≤100000,0≤M≤100000)，分别表示总人数和某些同学的偏好。
接下来MM行，每行两个整数AA 和B(1≤A,B≤N)B(1≤A,B≤N)，表示ID为AA的同学不希望ID为BB的同学排在他（她）之前。你可以认为题目保证至少有一种排列方法是符合所有要求的。

Output

对于每组数据，输出最大分数 。

Sample Input

3 1 0 2 1 1 2 3 1 3 1

Sample Output

1 2 6

解题思路：

显然越大的数字排在越前面的方案越好,所以在面临选择的情况下先把大的排在前面.因为排有些人的时候有依赖关系,这个关系相当于要符合一个拓扑序列.所以用优先队列维护入度为0的点,每次把最大的元素放到剩下位置的第一个就好了。

拓扑排序：

一.定义

​ 对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若 ∈E(G)，则u在线性序列中出现在v之前。

通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。

注意:

1)只有有向无环图才存在拓扑序列;

2)对于一个DAG,可能存在多个拓扑序列;

如:

该DAG的拓扑序列为A B C D或者A C B D

而此有向图是不存在拓扑序列的，因为图中存在环路

拓扑序列算法思想

(1)从有向图中选取一个没有前驱(即入度为0)的顶点，并输出之;

(2)从有向图中删去此顶点以及所有以它为尾的弧;

重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。

vector<int>g[100010];
int in[100010];
int main()
{
   int t,n,m,u,v;
   scanf("%d",&t);
   while(t--)
    {
       scanf("%d%d",&n,&m);
       for(int i=1;i<=n;i++)
       {
           g[i].clear();
           in[i]=0;
       }
       while(m--)
       {
           scanf("%d%d",&u,&v);
           g[u].push_back(v);
           in[v]++;
       }
       priority_queue<int>q;
       for(int i=1;i<=n;i++)
           if(in[i]==0)
                q.push(i);
       long long sum=0;
       long long MIN=INF;
       while(!q.empty())
       {
           int temp=q.top();
           q.pop();
           if(temp<MIN)MIN=temp;
            sum+=MIN;
           for(int i=0;i<g[temp].size();i++)
           {
                in[g[temp][i]]--;
               if(in[g[temp][i]]==0)q.push(g[temp][i]);//入度为0的点肯定在这里面
           }
       }
       printf("%lld\n",sum);
    }
   return 0;
}