Fişierul intrare/ieşire:	weightgraph.in, weightgraph.out	Sursă	FMI No Stress 10
Autor	Stelian Chichirim	Adăugată de	FMI No Stress 9 •fminostress9
Timp execuţie pe test	0.3 sec	Limită de memorie	323840 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Weight Graph

Se aproprie sarbatorile si trebuie sa cumperi cadouri! Se da un graf neorientat conex cu N noduri si M muchii. Tu te aflii in nodul 1 si vrei sa strangi K cadouri. Definim un drum valid un drum care pleaca din nodul 1 si nu contine 2 muchii consecutive identice. Costul unui astfel de drum este produsul valorilor muchiilor ce formeaza drumul. Numarul total de cadouri pe care le vei obtine este egal cu suma costurilor tuturor drumurilor valide din acest graf.
Astfel, trebuie sa ii asociati fiecarei muchii un cost mai mare sau egal ca 0 astfel incat numarul total de cadouri pe care le veti obtine sa fie exact K, iar dintre toate aceste posibile atriburi trebuie afisata o atribuire care are muchia de cost maxim minima posibila (trebuie minimizata muchia de cost maxim).

Date de intrare

Fişierul de intrare weightgraph.in contine pe prima linie N, M si K
Urmeaza M linii, fiecare avand 2 numere, X_i si Y_i, care semnifica ca exista muchie de la nodul X_i la nodul Y_i.

Date de ieşire

În fişierul de ieşire weightgraph.out se vor afisa M numere, fiecare pe cate o linie, astfel incat numarul de pe linia i reprezinta costul asociat muchiei dintre nodurile X_i si Y_i din fisierul de intrare.

Restricţii

• 2 ≤ N ≤ 100.000
• 1 ≤ M ≤ 200.000
• 1 $le; K &l; N
• 0 ≤ costul asociat unei muchii ≤ 10^9
• Pentru 20% din punctaj graful va avea forma de lant.
• Pentru alte 20% din punctaj N ≤ 1.000 si M ≤ 2.000.
• Pentru alte 60% din punctaj restrictiile initiale.
• Nu vor exista muchii multiple sau muchii de la un nod la acelasi nod.
• Daca exista mai multe solutii, puteti afisa oricare dintre ele.

Exemplu

Explicaţie

...

Cum se trimit solutii?