У 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