记录编号	436333	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HNOI 2015]菜肴制作	最终得分	100
用户昵称	Anonymity	是否通过	通过
代码语言	C++	运行时间	0.499 s
提交时间	2017-08-11 19:07:19	内存使用	2.60 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
#include<set>
#define maxn 100005
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
inline int read()
{   char c=getchar();int x=0,y=1;
	while(c<'0'||c>'9'){if(c=='-') y=-1;c=getchar();}
	while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	return x*y;
}
int t,n,m,num,hea[maxn],rin[maxn],ans[maxn],cnt,all;
struct road{int en,w,nex;}ro[maxn];
set<int>s;
void add(int x,int y){ro[num].en=y;ro[num].nex=hea[x];hea[x]=num++;}
int main()
{   freopen("dishes.in","r",stdin);
	freopen("dishes.out","w",stdout);
	t=read();
	while(t--)
	{	n=read();m=read();
		mem(hea,-1);mem(rin,0);
		num=0;cnt=0;all=0;int x,y;
		for(int i=1;i<=m;++i){x=read();y=read();add(y,x);++rin[x];}
		for(int i=n;i>=1;--i)
			if(!rin[i]) ++all,s.insert(i);
		int sz=s.size();
		while(sz)
		{	int u=*s.rbegin();s.erase(s.find(u));--sz;
			ans[++cnt]=u;
			for(int i=hea[u];i!=-1;i=ro[i].nex)
			{	int v=ro[i].en;--rin[v];
				if(!rin[v]) ++all,s.insert(v),++sz;
			}
		}
		if(all!=n) printf("Impossible!\n");
		else
		{	for(int i=cnt;i>=1;--i)
				printf("%d ",ans[i]);
			putchar('\n');
		}
	}
	return 0;
}