ソウル科学高校には $N$ 人の教師と $N$ 人の生徒がいます。明日は韓国の教師の日なので、生徒はそれぞれ $N$ 本の花を買いました。しかし、生徒のうち 1 人が退学したため、現在この学校には $N-1$ 人の生徒しか残っていません。

教師たちはとても嫉妬深く、ある生徒から受け取る花が他の教師より少ないと、その生徒に F の成績をつけてしまいます。したがって、各教師がちょうど $N-1$ 本の花を受け取る必要があります。生徒は自分を教えたことのある教師にしか花を渡せず、どの生徒がどの教師から教わったことがあるかは分かっています。

Younghun はソウル科学高校の生徒で、この行事を企画するためにあなたの助けを必要としています。

入力

最初の行には 2 つの整数 $N$ と $M$（$2 \le N \le 100 000$、$1 \le M \le 200 000$）が与えられます。これらは教師の人数と、生徒がその教師から教わったことのある（生徒、教師）の組の数を表します。

続く $M$ 行は関係を表します。第 $j$ 行には 2 つの整数 $s_j$、$t_j$（$1 \le s_j \le N-1$、$1 \le t_j \le N$）が与えられ、第 $s_j$ 番の生徒が第 $t_j$ 番の教師に花を渡せることを表します。すべての組が異なることが保証されます。

出力

すべての教師に同じ本数の花（$N-1$ 本）を渡すことが不可能なら、最初の行に数 $-1$ を 1 つ出力してください。

そうでなければ、プログラムは $M$ 行を出力してください。第 $j$ 行には、第 $s_j$ 番の生徒が第 $t_j$ 番の教師に渡した花の本数を表す整数を 1 つ出力してください。

答えが複数ある場合は、そのうちどれを出力してもかまいません。

入出力例

入力 1

6 12
1 3
1 4
1 5
2 2
2 4
3 1
3 3
4 1
4 2
4 4
5 4
5 6

出力 1

1
0
5
5
1
2
4
3
0
3
1
5

入力 2

6 12
1 2
1 3
1 4
2 2
2 4
3 1
3 3
4 1
4 2
4 4
5 5
5 6

出力 2

-1