Problem C
Changing Complexity

Creating star ship software modules and components isn’t easy, especially when the engineering and operations staff on those ships think it’s easy to maintain backwards compatibility. “Remodulate the deflector emitters”? “Reverse the polarity of the shield matrix”? The shield matrix was removed from the deflector shields $3$ versions ago! We gave them ample time to migrate their procedures and training to the newer quantum computers that now does the graviton flux analysis. We even said we could help out with documentation and resolving common procedures, but it turns out we just can’t teach an old dog new tricks…

To maintain the old ways of doing it, we’ve implemented a shield matrix translation layer so that they can use the same interface as they’ve always used. However, with the newer quantum computers changing their internal logic, we’ve been forced to rewrite the translation layer completely!

That being said, not everyone’s angry about maintaining a legacy interface. Our newest hire, Glaucia, actually seems to love maintenance and backwards compatibility work. And she’s very eager to get this to work.

While the rest of the team has taken a vacation at Sikaris, Glaucia wanted to take a stab at the rewrite project. Fortunately, the team’s been good at mapping up all the different tasks required to complete the rewrite, and has assigned all tasks their complexity and dependencies.

None of the rewrite tasks are too challenging for Glaucia. However, some of the tasks are quite boring. To avoid too much boredom at the same time, Glaucia has decided to complete the different tasks in alternating difficulty: They will first pick the least complex task of all the tasks they can perform, then pick the most complex task they can perform. They repeat this pattern until all tasks have been completed.

Glaucia can of course pick any task they want to, as long as it’s not been completed already, or some of its requirements have not yet been completed.

Of course, Glaucia managed to complete the entire rewrite project before the rest of the team came back from Sikaris. Unfortunately, the git history is a bit of a mess, and although it is not essential for anything, Glaucia’s manager wants to know which order they performed the tasks. Can you help their manager reconstruct which order Glaucia performed the tasks?

Input

The first line contains two integers, $V$ and $E$, the number of tasks and the number of different requirements, respectively. The complexity of a task is given by its ID: Task $1$ has $1$ complexity, task $2$ has $2$ complexity, and so on.

Then follow $E$ lines, each representing a requirement. Each line contains two integers, $u_ i$ and $v_ i$, indicating that task $v_ i$ can only be completed if $u_ i$ has been completed.

As the input may be very large, you should consider buffering it.

Output

Output

where $O_ i$ is the complexity of the $i^{th}$ task that was completed by Glaucia.

Limits

• $1 \leq V \leq 200\, 000$

• $0 \leq E \leq \min (400\, 000, \frac{V(V-1)}{2})$

• $0 < u_ i, v_ i \leq V$

• For all $i \neq j$: If $u_ i = u_ j$, then $v_ i \neq v_ j$

• The tasks form a forest of DAGs.

7 8
1 6
2 4
3 1
4 6
5 1
5 4
7 2
7 5

114

6 4
1 5
1 6
3 4
6 2

78

200 0

2025050