Fişierul intrare/ieşire:nogcd.in, nogcd.outSursăLot 2017 Baraj 1
AutorMihai CiucuAdăugată deeudanipEugenie Daniel Posdarascu eudanip
Timp execuţie pe test1 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Nogcd

Boss, dacă N e 30 000, clar încerci N2 optimizat! 
(Friedrich Nietzsche)

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.

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

  • 1 ≤ N ≤ 100 000
  • 1 ≤ M ≤ 220 000
  • Daca exista mai multe solutii, afisati oricare.
  • Se garanteaza ca mereu exista solutie.

Exemplu

nogcd.innogcd.out
5 6
1 2
2 3
1 3
4 1
3 4
3 5
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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?