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

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1000010;
int n, m, ans[MAXN], cnt, in[MAXN];
vector<int> cd[MAXN];
signed main() {
	freopen("dishes.in", "r", stdin);
	freopen("dishes.out", "w", stdout);
	int t;
	cin >> t;
	for(int tt = 1; tt <= t; tt ++) {
		cin >> n >> m;
		memset(in, 0, sizeof(in));
		for(int i = 1; i <= n; i ++) {
			cd[i].clear();
		}
		for(int i = 1; i <= m; i ++) {
			int x, y;
			cin >> x >> y;
			cd[y].push_back(x);
			in[x] ++;
		}
		priority_queue<int> q;
		for(int i = 1; i <= n; i ++) {
			if(!in[i]) {
				q.push(i);
			}
		}
		cnt = 0;
		int sum = 0;
		while(!q.empty()) {
			int u = q.top();
			q.pop();
			sum ++;
			ans[++ cnt] = u;
			for(int i = 0; i < cd[u].size(); i ++) {
				int v = cd[u][i];
				in[v] --;
				if(!in[v]) {
					q.push(v);
				}
			}
		}
		if(sum != n) {
			cout << "Impossible!" << endl;
			continue;
		}
		for(int i = n;  i >= 1; i --) {
			cout << ans[i] << ' ';
		}
		cout << endl;
	}
    return 0;
}