13891389 SUSTech Online Judge
Problem 1389 --Troublesome Long Queue

1389: Troublesome Long Queue

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 839  Solved: 170
[Submit][Status][Web Board]

Description

One day, a group student in SUSTech want to combine some paragraphs into an essay. It is a terrible job because the paragraphs are written by different people. Each paragraph has a index number.
As a result, they come up with an idea - put these paragraphs into a queue and pop them out sequently and they just need to consider how to combine the paragraph from the front of the queue into the essay in every iteration.
However, there are $$n$$ special regulations about the order of the paragraphs in the queue. Each regulation describes something like "paragraph $$a$$ must be in front of paragraph $$b$$" using the notation "$$a$$ $$b$$".
So it is your job to help them determine the order of the paragraphs in the queue.

Input

Line 1: Two integers $$n(2\le n\le10^5)$$ and $$m(1\le m\le10^5)$$, where $$n$$ indicates the number of paragraphs and $$m$$ indicates the number of regulations.
There are $$m$$ lines following:
Line 2~(m+1): Each line contains two integers $$a(1\le a\le n)$$ and $$b(1\le b\le n)$$, which means the paragraph $$a$$must be in front of paragraph $$b$$ in the queue.

Output

Print $$n$$ integers in range $$[1,n]$$ indicating the order of these $$n$$ paragraphs in queue.
If there are multiple answers, please output the one with the smallest lexicographic order.

3 3
1 2
2 3
1 3

1 2 3

HINT

The definition of lexicographic order can be found in the webpage: https://en.wikipedia.org/wiki/Lexicographic_order

[Submit][Status]