== include(page="template/taskheader" task_id="nogcd") ==
Poveste şi cerinţă...
bq. Boss, dacă N e 30 000, clar încerci N^2^ 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$.
h2. Date de intrare
Fişierul de intrare $nogcd.in$ ...
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$.
h2. Date de ieşire
În fişierul de ieşire $nogcd.out$ ...
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.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 100 000$
* $1 ≤ M ≤ 220 000$
* Daca exista mai multe solutii, afisati oricare.
* Se garanteaza ca mereu exista solutie.
h2. Exemplu
table(example). |_. nogcd.in |_. nogcd.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|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
|
h3. 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.
== include(page="template/taskfooter" task_id="nogcd") ==
