| Fişierul intrare/ieşire: | nogcd.in, nogcd.out | Sursă | Lot 2017 Baraj 1 |
| Autor | Mihai Ciucu | Adăugată de |  Eugenie Daniel Posdarascu •eudanip |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | nogcd.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.
