トポロジカルソート
閉路のない有向グラフDAG は物事の手順を表すデータ構造として応用することができます。例えば、各仕事を頂点、仕事の順序を有向辺で表すことができます。上の図では、仕事B に着手するためには、仕事A と仕事X の両方が完了している必要があります。このような関係を表すDAG に対して、トポロジカルソートを行うと、着手すべき順番に仕事を列挙することができます。DAG の各辺 $(u, v)$ について、$u$ が $v$ よりも先に位置するように並べることを、トポロジカルソートと言います。
与えられた DAG $G$ に対して、トポロジカルソートを行った頂点の並びを出力してください。
入力
入力は以下の形式で与えられます。
$|V|\;|E|$
$s_0 \; t_0$
$s_1 \; t_1$
:
$s_{|E|-1} \; t_{|E|-1}$
$|V|$, $|E|$ はそれぞれグラフ $G$ の頂点の数と辺の数を示します。グラフ $G$ の頂点はそれぞれ $0, 1, ..., |V|−1$ の番号が付けられているものとします。
$s_i$, $t_i$ はグラフ $G$ の $i$ 番目の有向辺が結ぶ２つの頂点の番号を表します。
出力
グラフ $G$ の頂点番号をトポロジカル順序で出力してください。各頂点の番号を１行に出力してください。
この問題では、１つの入力に対して複数の解答があります。条件を満たす出力は全て正解となります。
制約
- $1 \leq |V| \leq 10,000$
- $0 \leq |E| \leq 100,000$
- グラフ $G$ はDAG である
- グラフ $G$ に多重辺はない
- グラフ $G$ に自己ループはない
入力例
6 6 0 1 1 2 3 1 3 4 4 5 5 2
出力例
0 3 1 4 5 2