//bài toán:Có n công việc (đánh số từ 1 → n)
//Có m yêu cầu dạng (u, v) nghĩa là phải làm u trước v.
//In ra thứ tự làm các công việc thoả mãn m yêu cầu. Nếu không có cách, in IMPOSSIBLE
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> adj(n + 1);
vector<int> indegree(n + 1, 0);
// Đọc các yêu cầu
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
indegree[v]++;
}
queue<int> q;
// Đưa các công việc không có yêu cầu trước vào queue
for (int i = 1; i <= n; i++) {
if (indegree[i] == 0) {
q.push(i);
}
}
vector<int> topo_order;
while (!q.empty()) {
int u = q.front();
q.pop();
topo_order.push_back(u);
for (int v : adj[u]) {
indegree[v]--;
if (indegree[v] == 0) {
q.push(v);
}
}
}
// Nếu chưa lấy đủ n đỉnh nghĩa là có chu trình, có 1 tập các công việc bị phụ thuộc vào nhau
if ((int)topo_order.size() != n) {
cout << "IMPOSSIBLE\n";
} else {
for (int x : topo_order) {
cout << x << " ";
}
cout << "\n";
}
return 0;
}
Ly9iw6BpIHRvw6FuOkPDsyBuIGPDtG5nIHZp4buHYyAoxJHDoW5oIHPhu5EgdOG7qyAxIOKGkiBuKQovL0PDsyBtIHnDqnUgY+G6p3UgZOG6oW5nICh1LCB2KSBuZ2jEqWEgbMOgIHBo4bqjaSBsw6BtIHUgdHLGsOG7m2Mgdi4KLy9JbiByYSB0aOG7qSB04buxIGzDoG0gY8OhYyBjw7RuZyB2aeG7h2MgdGhv4bqjIG3Do24gbSB5w6p1IGPhuqd1LiBO4bq/dSBraMO0bmcgY8OzIGPDoWNoLCBpbiBJTVBPU1NJQkxFIAojaW5jbHVkZSA8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBtYWluKCkgewogICAgaW9zOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwogICAgY2luLnRpZShudWxscHRyKTsKCiAgICBpbnQgbiwgbTsKICAgIGNpbiA+PiBuID4+IG07CgogICAgdmVjdG9yPHZlY3RvcjxpbnQ+PiBhZGoobiArIDEpOwogICAgdmVjdG9yPGludD4gaW5kZWdyZWUobiArIDEsIDApOwoKICAgIC8vIMSQ4buNYyBjw6FjIHnDqnUgY+G6p3UKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbTsgaSsrKSB7CiAgICAgICAgaW50IHUsIHY7CiAgICAgICAgY2luID4+IHUgPj4gdjsKICAgICAgICBhZGpbdV0ucHVzaF9iYWNrKHYpOwogICAgICAgIGluZGVncmVlW3ZdKys7CiAgICB9CgogICAgcXVldWU8aW50PiBxOwoKICAgIC8vIMSQxrBhIGPDoWMgY8O0bmcgdmnhu4djIGtow7RuZyBjw7MgecOqdSBj4bqndSB0csaw4bubYyB2w6BvIHF1ZXVlCiAgICBmb3IgKGludCBpID0gMTsgaSA8PSBuOyBpKyspIHsKICAgICAgICBpZiAoaW5kZWdyZWVbaV0gPT0gMCkgewogICAgICAgICAgICBxLnB1c2goaSk7CiAgICAgICAgfQogICAgfQoKICAgIHZlY3RvcjxpbnQ+IHRvcG9fb3JkZXI7CgogICAgd2hpbGUgKCFxLmVtcHR5KCkpIHsKICAgICAgICBpbnQgdSA9IHEuZnJvbnQoKTsKICAgICAgICBxLnBvcCgpOwogICAgICAgIHRvcG9fb3JkZXIucHVzaF9iYWNrKHUpOwoKICAgICAgICBmb3IgKGludCB2IDogYWRqW3VdKSB7CiAgICAgICAgICAgIGluZGVncmVlW3ZdLS07CiAgICAgICAgICAgIGlmIChpbmRlZ3JlZVt2XSA9PSAwKSB7CiAgICAgICAgICAgICAgICBxLnB1c2godik7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CgogICAgLy8gTuG6v3UgY2jGsGEgbOG6pXkgxJHhu6cgbiDEkeG7iW5oIG5naMSpYSBsw6AgY8OzIGNodSB0csOsbmgsIGPDsyAxIHThuq1wIGPDoWMgY8O0bmcgdmnhu4djIGLhu4sgcGjhu6UgdGh14buZYyB2w6BvIG5oYXUKICAgIGlmICgoaW50KXRvcG9fb3JkZXIuc2l6ZSgpICE9IG4pIHsKICAgICAgICBjb3V0IDw8ICJJTVBPU1NJQkxFXG4iOwogICAgfSBlbHNlIHsKICAgICAgICBmb3IgKGludCB4IDogdG9wb19vcmRlcikgewogICAgICAgICAgICBjb3V0IDw8IHggPDwgIiAiOwogICAgICAgIH0KICAgICAgICBjb3V0IDw8ICJcbiI7CiAgICB9CgogICAgcmV0dXJuIDA7Cn0=