Problem Solving Order

Interview

Time limit2sMemory limit128 MB

Summary
Given N tasks and M precedence constraints, output a topological order that always picks the smallest available problem number next.
Level

Medium4 of 10

Topics
Topological sort, Heap, Graph
Solved
No attempts yet

Problem

Mino plans to solve all N problems numbered from 1 to N. A smaller number means an easier problem: problem 1 is the easiest, and problem N is the hardest.

While reviewing the problems, Mino found that some problems become easier after solving certain other problems first. Mino wants to choose an order that satisfies these rules.

  1. Solve each of the N problems exactly once.
  2. If the input says problem A should be solved before problem B, then A must be solved before B.
  3. While satisfying the previous rules, whenever several problems can be solved next, choose the problem with the smallest number.

Given the number of problems and the before relations, write a program that outputs the order in which Mino should solve the problems.

Input

The first line contains the number of problems N (1 ≤ N ≤ 32,000) and the number of before relations M (1 ≤ M ≤ 100,000).

Each of the next M lines contains two integers A and B separated by a space. This means problem A should be solved before problem B.

The input is always such that all problems can be solved.

Output

On the first line, output the problem numbers from 1 to N in the order Mino should solve them, separated by spaces.

Examples1

  1. Example 1

    Input
    4 2
4 2
3 1
    Expected output
    3 1 4 2