记录编号	575846	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HNOI 2015]菜肴制作	最终得分	100
用户昵称	Skloud	是否通过	通过
代码语言	C++	运行时间	1.452 s
提交时间	2022-09-28 21:44:20	内存使用	3.84 MiB

#include <bits/stdc++.h>
using namespace std;
const int N=100000+5;
struct sdf{
    int to,next;
}eg[2*N];
int head[N]={0},ne=0;
int n,m,in[N];
bool vis[N];
int ans[N],cnt=0;
void add(int x,int y){
    eg[++ne]={y,head[x]};
    head[x]=ne;in[y]++;
    return ;
}
priority_queue<int>q; 
int main(){
	freopen ("dishes.in","r",stdin);
	freopen ("dishes.out","w",stdout);
	int T;scanf("%d",&T);
	while(T--){
	    scanf("%d%d",&n,&m);
	    ne=0;cnt=0;
	    for (int i=1;i<=n;i++)head[i]=in[i]=vis[i]=0;
	    for (int i=1;i<=m;i++){
	        int x,y;scanf("%d%d",&x,&y);
	        add(y,x);
	        if (x==y)cnt=-1;
        }
        if (cnt==-1){
            printf("Impossible!\n");continue;
        }
        for (int i=1;i<=n;i++){
            if (!in[i])q.push(i);
        }
        while(!q.empty()){
            int u=q.top();q.pop();ans[++cnt]=u;
            for (int i=head[u];i!=0;i=eg[i].next){
                int v=eg[i].to;
                in[v]--;
                if (!in[v])q.push(v);
            }
        }
        if (cnt!=n){
            printf("Impossible!\n");continue;
        }
        for (int i=n;i>=1;i--)printf("%d ",ans[i]);
        printf("\n");
    }
    return 0;
}