== include(page="template/taskheader" task_id="oz") ==
Poveste si cerinta...
In taramul fermecat din Oz exista un vrajitor care are ca scop salvarea lumii. Fortele malefice incearca insa sa il impiedice si, pentru aceasta, il provoaca pe vrajitor la un joc al carui castigator va decide soarta lumii. Astfel, fortele raului aleg la intamplare un vector de $N$ numere naturale nenule si ii transmit vrajitorului $M$ triplete de forma {$(i j d)$}, cu semnificatia ca cel mai mare divizor comun dintre al $i$-lea si al $j$-lea numar din vector este {$d$}. Scopul jocului este ca, pornind de la cele $M$ triplete, sa se gaseasca vectorul initial. In cazul in care fortele raului triseaza si nu exista nicio solutie, sa se precizeze acest lucru.
h2. Date de intrare
Fisierul de intrare $oz.in$ ...
Fisierul de intrare $oz.in$ contine pe prima linie numerele $N$ si $M$, separate prin exact un spatiu. Urmatoarele $M$ linii contin cate un triplet de forma {$(i j d)$}, cu semnificatia din enunt.
h2. Date de iesire
In fisierul de iesire $oz.out$ ...
Fisierul de iesire $oz.out$ va contine o singura linie, pe care se vor afla $N$ numere naturale, indicand o posibila solutie. Solutia trebuie sa aiba in plus proprietatea ca fiecare numar din cele $N$ nu depaseste $2$ miliarde. Se garanteaza ca daca exista solutie, va exista cel putin una care sa indeplineasca aceasta proprietate. In cazul in care nu exista nicio solutie se va afisa doar {$-1$}.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 10 000$
* $1 ≤ M ≤ 100 000$
* Pentru orice triplet {$(i j d)$} are loc: $1 ≤ i, j ≤ N$, $i$ diferit de $j$ si {$1 ≤ d ≤ 2 000 000 000$}
h2. Exemplu
table(example). |_. oz.in |_. oz.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
|4 3
1 4 2
2 3 5
1 3 6
|12 5 30 14|
h3. Explicatie
...
Cel mai mare divizor comun intre $12$ si $14$ este {$2$}, intre $5$ si $30$ este {$5$}, iar intre $12$ si $30$ este {$6$}, deci aceste numere reprezinta o solutie deoarece indeplinesc toate conditiile din enunt.
== include(page="template/taskfooter" task_id="oz") ==
