| Fişierul intrare/ieşire: | oz.in, oz.out | Sursă | preONI 2008, Runda finala |
| Autor | Filip Cristian Buruiana | Adăugată de |  Filip Cristian Buruiana •filipb |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 8192 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Oz
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.
Date de intrare
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.
Date de iesire
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.
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
Exemplu
| oz.in | oz.out |
|---|---|
| 4 3 1 4 2 2 3 5 1 3 6 | 12 5 30 14 |
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.
