第一眼看到這題，頓時懵逼，一個 \(SB\) 拓撲序竟然是黑題，當場笑噴。
\(Of\) \(course\)，這題我是用堆做的。（其實是優先隊列，手寫堆這么垃圾我怎么可能會用呢）
\((1)\) 首先建圖。如果 \(x\) 需要在 \(y\) 前面，就從 \(y\) 向 \(x\) 連邊。
\((2)\) 然后把沒有入邊的點先加入堆。每次從堆中取出最小的數記下來。
\((3)\) 然后把它連向的點全都入堆。直到堆空。如果取出的點不是 \(n\) 個就輸出不可能。否則輸出記下來的點就好了。
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAX_N=100010;
struct EDGE{int v,nxt;
}e[MAX_N];
int d,n,m,in[MAX_N],cnt,head[MAX_N],a[MAX_N];
priority_queue<int> q;
inline int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-'){f=-1;}c=getchar();}while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f;
}
void add(int u,int v){e[++cnt].v=v;e[cnt].nxt=head[u];head[u]=cnt;
}
bool bfs(){while(!q.empty()){int p=q.top();q.pop();cnt++;a[cnt]=p;for(int i=head[p];i;i=e[i].nxt){int v=e[i].v;in[v]--;if(!in[v]){q.push(v);}}}return cnt==n;
}
int main(){d=read();while(d--){memset(in,0,sizeof(in));memset(head,0,sizeof(head));cnt=0;n=read(),m=read();for(int i=1;i<=m;i++){int x,y;x=read(),y=read();add(y,x);in[x]++;}for(int i=1;i<=n;i++){if(!in[i]){q.push(i);}}cnt=0;if(bfs()){for(int i=n;i>=1;i--){printf("%d ",a[i]);}printf("\n");}else{printf("Impossible!\n");}}return 0;
}
/*
3
5 4
5 4
5 3
4 2
3 2
3 3
1 2
2 3
3 1
5 2
5 2
4 3 1 5 3 4 2
Impossible!
1 5 2 4 3
*/
