不妨认为我们这样得到的不是最优解，那么令这样得到的序列为a，然后最优解是b。

我们从后往前开始找到第一位两个序列不同的一位设为k，那么a[k]!=b[k]，且a[k]>b[k]。（由a的构造方式可知）（先假设这个k存在，再证出矛盾）

再设a[k]出现的b的p位置，即b[p]=a[k]。再设b[p] b[p+]……b[k]这个子序列为C。

那么b[p]一定不是C中的最小元素，因为有b[k]<b[p]=a[k]。

然后不妨设b[q]为C的最小元素。然后我们把b[p]移到b[k]的位置，得到序列bb。

如果bb合法的话，那么我们就得到了一个比b优的解，这与b是最优解矛盾。

（因为b[q]的位置前移了一位，我们要求编号小的尽可能靠前）

但bb显然是合法的。因为在a序列中k以及后面的是合法的，那么b后面也这么做一定也是合法的。

所以一定不存在某个k，使得a[k]!=b[k]。也就是说a=b。

所以算法正确性得证。

 #include<bits/stdc++.h>

 using namespace std;

 const int MAXN=+;

 int n,m,in;

 vector<int> E[MAXN];

 priority_queue<int> que;

 int ans[MAXN],inn[MAXN];

 void init()

 {

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

     memset(inn,,sizeof(inn));

     for (int i=;i<=n;i++) vector<int>().swap(E[i]);

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

     {

         int u,v;

         scanf("%d%d",&u,&v);

         inn[u]++;

         E[v].push_back(u);

     }

 }

 void solve()

 {

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

     ans[]=;

     for (int i=;i<=n;i++) if (!inn[i]) que.push(i);

     while (!que.empty())

     {

         int u=que.top();que.pop();

         ans[++ans[]]=u;

         for (int i=;i<E[u].size();i++)

         {

             int v=E[u][i];

             inn[v]--;

             if (!inn[v]) que.push(v);

         }

     }

     if (ans[]<n) puts("Impossible!");

         else

         {

             for (int i=ans[];i>=;i--) printf("%d ",ans[i]);

             printf("\n");

         }

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     while (T--)

     {

         init();

         solve();

     }

     return ;

 }