Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Minimal Labels

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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*label*_{v}should be smaller than*label*_{u}. - 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* ≤ 10^{5}, 1 ≤ *m* ≤ 10^{5}).

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

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/27/2023 14:18:21 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|