| Author: | A. Klenin, I. Tuphanov | Time limit: | 1 sec | |
| Input file: | input.txt | Memory limit: | 256 Mb | |
| Output file: | output.txt |
Once upon a time in a galaxy far, far away there was a planet with an extensive government of N officials. Some officials were subordinates of others.
The main task of the government were to implement innovations. Each innovation was implemented in the following way: first, the innovation, along with some budget, is assigned to one of the officials. The official takes some of the budget and reassigns the innovation to one of his subordinates. This process repeats until innovation reaches the official without subordinates, who takes the remaining budget. At this point, innovation is declared to be implemented.
The government considers the innovation to be optimally implemented if every official is involved in the implementation.
Your program must, given the superior-subordinate relationships, find an order in which officials should be involved in the optimal implementation of the innovation.
Input file contains integers N M, followed by M pairs of integers ui vi. Each pair designates that the official number vi is subordinate of the official number ui (1 ≤ ui, vi ≤ N, ui ≠ vi).
It is guaranteed that there are no cycles in the superior-subordinate relationship.
Output file must contain N integers — numbers of officials in the order they should process the innovation. If there is no solution, output single number 0. If there is more that one solution, output any of them.
| No. | Input file (input.txt) |
Output file (output.txt) |
|---|---|---|
| 1 |
|
|
| 2 |
|
|