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