Problem 1389 --Troublesome Long Queue1389: 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.
Sample Input
3 3
1 2
2 3
1 3
Sample Output
1 2 3
HINT
Source
[Submit][Status]