O-Speleologists
Naši speleolozi Toma i Miloš saznali su iz pouzdanih izvora da u kod “Tri Brežuljka” u blizini Sombora postoji ulaz u pecinu koja vodi skoro do središta zemlje. No njih to ne interesuje toliko koliko žele da udu u ginisovu knjigu rekorda sa najvecom osvojenom dubinom.
Sistem u kom su se našli cini N dvorana i N-1 puteva. Prva dvorana, oznacena sa brojem 1, je odmah na ulazu i smatracemo da je ona na dubini 0. Iz svake dvorane je moguc proizvoljan broj puteva do isto toliko dvorana na nekoj vecoj dubini. Do svake dvorane se može doci samo na jedan nacin.
Image: mapa
InputU prvom redu standardnog ulaza nalaze se broj N. U sledecih N-1 redova nalaze se po tri cela broja D1, D2 i VR.
D1 i D2 predstavljaju brojeve dvorana (D1 <> D2) a VR je visinska razlika izmedu te dve dvorane.
Svi brojevi koji se pojavljuju na ulazu zadatka - (1 <= N, D1, D1, VR <= 100 000)
D1 i D2 predstavljaju brojeve dvorana (D1 <> D2) a VR je visinska razlika izmedu te dve dvorane.
Svi brojevi koji se pojavljuju na ulazu zadatka - (1 <= N, D1, D1, VR <= 100 000)
OutputU prvi red standardnog izlaza potrebno je ispisati najveca dubina do koje speleolozi mogu stici. U sledecih K redova putanju od prve pa do poslednje dvorane na najdužem putu. Ulazni podaci ce biti takvi, da je rešenje jedinstveno.
Ulaz:
Izlaz:
15
1 2 5
6 2 7
11 2 6
2 7 11
1 3 11
12 3 4
1 4 2
4 8 12
5 1 4
5 10 4
5 9 1
14 10 4
13 9 8
13 15 2Izlaz:
16
1
2
7Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.