Fişierul intrare/ieşire:oz.in, oz.outSursăpreONI 2008, Runda finala
AutorFilip Cristian BuruianaAdăugată defilipbFilip Cristian Buruiana filipb
Timp execuţie pe test0.1 secLimită de memorie8192 kbytes
Scorul tăuN/ADificultateN/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.inoz.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content