arb4

Arb4

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

Poveste şi cerinţă...

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

Fişierul de intrare $arb4.in$ ...

Fişierul de intrare $arb4.in$ va contine pe prima linie $2$ numere naturale $N$ si $M$. Pe urmatoarele $M$ linii se vor afla $3$ numere naturale $a b c$ reprezentand ca avem o muchie de la $a$ la $b$ de cost $c$. Primele $N - 1$ muchii din cele $M$ formeaza arborele initial.

h2. Date de ieşire

În fişierul de ieşire $arb4.out$ ...

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$
* 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
table(example). |_. arb4.in |_. arb4.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 5 10
3 2 1
4 2 2
0 3 3
1 4 4
0 4 456867131
1 3 33364433
0 1 49309036
3 4 975587959
0 2 139619699
2 1 767959053
| 5
5
6
5

|

h3. Explicaţie
 
...

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