Problem Description

糟糕的事情发生啦，现在大家都忙着逃命。但是逃命的通道很窄，大家只能排成一行。



现在有n个人，从1标号到n。同时有一些奇怪的约束条件，每个都形如：a必须在b之前。

同时，社会是不平等的，这些人有的穷有的富。1号最富，2号第二富，以此类推。有钱人就贿赂负责人，所以他们有一些好处。



负责人现在可以安排大家排队的顺序，由于收了好处，所以他要让1号尽量靠前，如果此时还有多种情况，就再让2号尽量靠前，如果还有多种情况，就让3号尽量靠前，以此类推。



那么你就要安排大家的顺序。我们保证一定有解。

 

Input

第一行一个整数T(1 <= T <= 5),表示测试数据的个数。

然后对于每个测试数据，第一行有两个整数n(1 <= n <= 30000)和m(1 <= m <= 100000)，分别表示人数和约束的个数。



然后m行，每行两个整数a和b，表示有一个约束a号必须在b号之前。a和b必然不同。

 

Output

对每个测试数据，输出一行排队的顺序，用空格隔开。

 

Sample Input

1

5 10

3 5

1 4

2 5

1 2

3 4

1 4

2 3

1 5

3 5

1 2

 

Sample Output

1 2 3 4 5
#include<iostream>

#include<queue>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<vector>

#include<stack>

#include<cstring>

#include<string>

#include<cstdlib>

using namespace std;

#define NN 30005

int from[NN],n,m,ans[NN];

struct node

{

    int people;

    friend bool operator <(node x,node y)

    {

        return x.people<y.people;

    }

};

priority_queue<node>q;

vector<int> mapp[NN];

void slove()

{

    int i,now,id=1;

    node c,d;

    for(i=n; i>0; i--)

    {

        if(from[i]==0)

        {

            c.people=i;

            q.push(c);

        }

    }

    while(!q.empty())

    {

        c=q.top();

        ans[id++]=c.people;

        q.pop();

        for(i=0; i<mapp[c.people].size(); i++)

        {

            from[mapp[c.people][i]]--;

            if(from[mapp[c.people][i]]==0)

            {

                d.people=mapp[c.people][i];

                q.push(d);

                // from[i]=-1;

            }

        }

    }

    while(!q.empty()) q.pop();

    for(i=1; i<=n; i++)

        mapp[i].clear();

}

int main(void)

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        int i;

        scanf("%d %d",&n,&m);

        memset(from,0,sizeof(from));

        for(i=0; i<m; i++)

        {

            int x,y;

            scanf("%d %d",&y,&x);

            from[y]++;

            mapp[x].push_back(y);

        }

        slove();

        for(i=n; i>1; i--)

            printf("%d ",ans[i]);

        printf("%d",ans[1]);

        printf("\n");

    }

    return 0;

}

// 逆向建边  拓扑排序   倒着来