В Seoul Science High School есть $N$ учителей и $N$ учеников. Каждый ученик купил $N$ цветов, потому что завтра в Корее День учителя. Однако один из учеников ушёл из школы, и теперь в ней осталось только $N-1$ учеников.

Учителя очень завистливы, поэтому они поставят ученику оценку F, если получат от него меньше цветов, чем другие учителя. Поэтому каждый учитель должен получить ровно $N-1$ цветов. Ученик может дарить цветы только тем учителям, которые его учили, и вам известно, какие ученики учились у каких учителей.

Younghun — ученик Seoul Science High School, и ему нужна ваша помощь в организации этого мероприятия.

Входные данные

Первая строка содержит два целых числа $N$ и $M$ ($2 \le N \le 100 000$, $1 \le M \le 200 000$), обозначающих число учителей и число пар (ученик, учитель), в которых ученик учился у учителя.

Следующие $M$ строк описывают отношения: $j$-я строка содержит два целых числа $s_j$, $t_j$ ($1 \le s_j \le N-1$, $1 \le t_j \le N$), означающих, что $s_j$-й ученик может подарить цветы $t_j$-му учителю. Гарантируется, что все пары различны.

Выходные данные

Если невозможно подарить всем учителям одинаковое число цветов ($N-1$ цветов), выведите в первой строке одно число $-1$.

Иначе ваша программа должна вывести $M$ строк. В $j$-й строке должно находиться одно целое число, обозначающее количество цветов, которые $s_j$-й ученик подарил $t_j$-му учителю.

Если существует несколько возможных ответов, можно вывести любой из них.

Примеры

Входные данные 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