You are given a directed acyclic graph with n vertices and m edges. There are no self-loops or multiple edges between any pair of vertices. Graph can be disconnected.
You should assign labels to all vertices in such a way that:
- Labels form a valid permutation of length n — an integer sequence such that each integer from 1 to n appears exactly once in it.
- If there exists an edge from vertex v to vertex u then labelv should be smaller than labelu.
- Permutation should be lexicographically smallest among all suitable.
Find such sequence of labels to satisfy all the conditions.
Input
The first line contains two integer numbers n, m (2 ≤ n ≤ 105, 1 ≤ m ≤ 105).
Next m lines contain two integer numbers v and u (1 ≤ v, u ≤ n, v ≠ u) — edges of the graph. Edges are directed, graph doesn't contain loops or multiple edges.
Output
Print n numbers — lexicographically smallest correct permutation of labels of vertices.
Examples
Input
3 3 1 2 1 3 3 2
Output
1 3 2
Input
4 5 3 1 4 1 2 3 3 4 2 4
Output
4 1 2 3
Input
5 4 3 1 2 1 2 3 4 5
Output
3 1 2 4 5
题目大意 给定一个有向无环图，用1~n为所有顶点标号，每个顶点的标号互不相同，如果有有一条边从v连向u，则v的标号应比u小，输出字典序最小的标号方案。
poj有一道一样的题，题解请戳这里。
Code
/**
* Codeforces
* Problem#825E
* Accepted
* Time: 46ms
* Memory: 5300k
*/
#include <bits/stdc++.h>
#ifndef WIN32
#define Auto "%lld"
#else
#define Auto "%I64d"
#endif
using namespace std;
typedef bool boolean;
const signed int inf = (signed)((1u << ) - );
const double eps = 1e-;
const int binary_limit = ;
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
template<typename T>
inline boolean readInteger(T& u){
char x;
int aFlag = ;
while(!isdigit((x = getchar())) && x != '-' && x != -);
if(x == -) {
ungetc(x, stdin);
return false;
}
if(x == '-'){
x = getchar();
aFlag = -;
}
for(u = x - ''; isdigit((x = getchar())); u = (u << ) + (u << ) + x - '');
ungetc(x, stdin);
u *= aFlag;
return true;
} ///map template starts
typedef class Edge{
public:
int end;
int next;
Edge(const int end = , const int next = -):end(end), next(next){}
}Edge; typedef class MapManager{
public:
int ce;
int *h;
vector<Edge> edge;
MapManager(){}
MapManager(int points):ce(){
h = new int[(const int)(points + )];
memset(h, -, sizeof(int) * (points + ));
}
inline void addEdge(int from, int end){
edge.push_back(Edge(end, h[from]));
h[from] = ce++;
}
inline void addDoubleEdge(int from, int end){
addEdge(from, end);
addEdge(end, from);
}
Edge& operator [] (int pos) {
return edge[pos];
}
inline void clear() {
edge.clear();
delete[] h;
}
}MapManager;
#define m_begin(g, i) (g).h[(i)]
#define m_endpos -1
///map template ends int n, m;
MapManager g;
int* dag;
int* dep; inline boolean init() {
if(!readInteger(n)) return false;
readInteger(m);
g = MapManager(n);
dag = new int[(n + )];
dep = new int[(n + )];
memset(dag, , sizeof(int) * (n + ));
for(int i = , a, b; i <= m; i++) {
readInteger(a);
readInteger(b);
g.addEdge(b, a);
dag[a]++;
}
return true;
} priority_queue<int> que;
inline void topu() {
for(int i = ; i <= n; i++)
if(!dag[i]) {
que.push(i);
}
int cnt = ;
while(!que.empty()) {
int e = que.top();
dep[e] = cnt++;
que.pop();
for(int i = m_begin(g, e); i != m_endpos; i = g[i].next) {
int& eu = g[i].end;
dag[eu]--;
if(!dag[eu])
que.push(eu);
}
}
} inline void solve() {
topu();
for(int i = ; i <= n; i++)
printf("%d ", n - dep[i]);
} int main() {
init();
solve();
return ;
}