bq. Boss, dacă N e 30 000, clar încerci N^2^ optimizat!
(Friedrich Nietzsche)

Se dă un graf conex fără bucle cu $N$ noduri şi $M$ muchii. Să se eticheteze fiecare muchie cu câte un număr de la $1$ la $M$ astfel încât să nu existe două muchii cu aceeaşi etichetă şi pentru fiecare nod cu grad mai mare decât $1$, cel mai mare divizor comun al etichetelor muchiilor incidente să fie $1$.

Se dă un graf conex fără bucle (muchii de la acelasi nod la acelasi nod) cu $N$ noduri şi $M$ muchii. Să se eticheteze fiecare muchie cu câte un număr de la $1$ la $M$ astfel încât să nu existe două muchii cu aceeaşi etichetă şi pentru fiecare nod cu grad mai mare decât $1$, cel mai mare divizor comun al etichetelor muchiilor incidente să fie $1$.

h2. Date de intrare

* $1 ≤ N ≤ 100 000$
* $1 ≤ M ≤ 220 000$

* Daca exista mai multe solutii, afisati oricare.
* Se garanteaza ca mereu exista solutie.

h2. Exemplu

Graful are $5$ noduri şi $6$ muchii.
Pentru nodul $1$ etichetele sunt $2, 1$ şi $3$, $cmmdc(2,1,3) = 1.$

Pentru nodul $2$ etichetele sunt  $2$ şi $5.$

Pentru nodul $2$ etichetele sunt $2$ şi $5.$

$cmmdc(2,5) = 1.$

Pentru nodul $3$ etichetele sunt  $3, 4, 5$  şi $6.$

Pentru nodul $3$ etichetele sunt $3, 4, 5$  şi $6.$

$cmmdc(3,4,5,6) = 1.$

Pentru nodul $4$ etichetele sunt  $1$ şi $4.$

Pentru nodul $4$ etichetele sunt $1$ şi $4.$

$cmmdc(1,4) = 1.$
Nodul $5$ are gradul $1$, deci nu se calculează cmmdc.