偶然间翻到三个月前写的这个题，发现现有的题解均未给出解法的正确性证明，只是不明不白地写了一些对理解做法毫无帮助的话。我认为解法的正确性并不显然，因此这篇题解主要给出正确性证明，补上逻辑漏洞。
解法与其他题解一样，即：建反图，然后跑拓扑排序，每次优先取出可以取出的编号最大的点，从 \(n\) 到 \(1\) 赋权值。
这似乎有点反直觉：为什么倒着做就恰好能满足字典序最小呢？相信大多数人的第一反应都是正着做，这也是我认为正确性并不显然的原因。
证明：
以下“入边”“出边”“入度”“出度”等均为原图上的。
考虑整个算法的第一步，也就是分配权值 \(n\)。显然，权值 \(n\) 的点出度必须为 \(0\)。
我们记在上述算法中，被分配了权值 \(n\) 的点的编号为 \(u\)。利用反证法，假设在另一种分配方案中，\(u\) 被分配了权值 \(x\)（\(x < n\)），而 \(v\) 被分配了权值 \(n\)。由于算法中取出的 \(u\) 是编号最大的出度为 \(0\) 的点，而 \(v\) 的出度也必须为 \(0\)，因此我们有 \(u > v\)。
对于这种分配方案中被分配权值 \(x+1\sim n\) 的点，我们可以将它们重新分配 \(x\sim n-1\) 的权值，并将 \(u\) 重新分配 \(n\) 的权值，仍然得到合法的分配方案。这是因为：点 \(u\) 出度为 \(0\)，将 \(u\) 的权值增大并不会影响 \(u\) 与其余节点的合法性；并且考虑去掉点 \(u\) 的其他节点，重新分配权值相当于对原来的权值进行离散化，不改变偏序关系。
因此，我们可以重新分配权值使得 \(u\) 的权值为 \(n\)。并且，由于 \(u > v\)，重新分配权值后答案的字典序减小。
由于点 \(u\) 的出度为 \(0\)，给它分配了最大的权值 \(n\) 之后，其余节点与 \(u\) 之间必然合法，只需要求出其余节点的最小字典序答案即可。因此将点 \(u\) 以及它的所有入边都删除，得到规模为 \(n-1\) 的子问题。又显然当 \(n=1\) 时，算法可以给出最小字典序答案，因此算法正确性得证。\(\square\)
//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
#define likely(exp) __builtin_expect(!!(exp), 1)
#define unlikely(exp) __builtin_expect(!!(exp), 0)
using namespace std;
typedef long long ll;
const int N = 1e5+5;
int n, m, deg[N], id[N], tms;
vector<int> e[N];
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
void toposort() {
priority_queue<int> q;
rep(i, 1, n) if(!deg[i]) q.push(i);
while(!q.empty()) {
int u = q.top(); q.pop();
id[u] = ++tms;
for(int v : e[u]) if(!--deg[v]) q.push(v);
}
}
int main() {
scanf("%d%d", &n, &m);
rep(i, 1, m) {
int u, v;
scanf("%d%d", &u, &v);
e[v].push_back(u);
++deg[u];
}
toposort();
rep(i, 1, n) printf("%d%c", n+1-id[i], " \n"[i==n]);
return 0;
}