Boss, dacă N e 30 000, clar încerci 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.
Date de intrare
Fișierul nogcd.in conține pe prima linie numerele naturale N și M separate printr-un spațiu, iar pe următoarele M linii se află câte două numere x și y separate prin câte un spațiu, între 1 și N, care înseamnă că există muchie între nodurile x și y.
Date de ieșire
Fișierul nogcd.out va conține M linii, pe fiecare linie conținând trei numere naturale x y v separate prin câte un spațiu, reprezentând extremitățile muchiei (x, y) și valoarea etichetei acestei muchii.
Restricții și precizări
1 ≤ N ≤ 100 0001 ≤ M ≤ 220 000
Exemplu
nogcd.in
5 6
1 2
2 3
1 3
4 1
3 4
3 5
nogcd.out
1 2 2
1 4 1
1 3 3
3 2 5
3 4 4
3 5 6
Explicație
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; cmmdc(2,5)=1.
Pentru nodul 3 etichetele sunt 3, 4, 5 și 6; cmmdc(3,4,5,6)=1.
Pentru nodul 4 etichetele sunt 1 și 4; cmmdc(1,4)=1.
Nodul 5 are gradul 1, deci nu se calculează cmmdc .