== include(page="template/taskheader" task_id="arb4") ==

Se da un graf cu $N$ noduri si $M$ muchii. Primele $N - 1$ muchii formeaza un arbore partial de cost minim. Pentru fiecare muchie $i$ din arbore trebuie sa se spuna in cazul in care muchia $i$ este stearsa, cu ce muchie trebuie inlocuita astfel incat costul arborelui partial sa fie minim.

Se da un graf cu $N$ noduri si $M$ muchii. Primele $N - 1$ muchii formeaza un arbore partial de cost minim. Pentru fiecare muchie $i$ din arbore trebuie sa se spuna in cazul in care muchia $i$ este stearsa, cu ce muchie trebuie inlocuita astfel incat costul arborelui partial sa fie minim.

h2. Date de intrare

h2. Date de ieşire

Fişierul de ieşire $arb4.out$ va contine $N - 1$ linii. Pe linia $i$ se va afla indicele muchiei care ar fi folosita daca am elimina muchia $i$ din arbore.

Fişierul de ieşire $arb4.out$ va contine $N - 1$ linii. Pe linia $i$ se va afla indicele muchiei care ar fi folosita daca am elimina muchia $i$ din arbore. Daca muchia $i$ nu poate sa fie inlocuita afisati $-1$.

h2. Restricţii
* $1 ≤ N ≤ 100.000$
* $1 ≤ M ≤ 250.000$

* toate muchiile au costuri distincte

* muchiile au costuri distincte doua cate doua din intervalul $[1,1.000.000.000]$

* primele $N - 1$ muchii formeaza un arbore partial de cost minim in graful dat
* nodurile si muchiile sunt numerotate de la $0$

* intre oricare doua noduri exista cel mult o muchie si nu exista muchie de la un nod la el insusi

h2. Exemplu