z-vidre

Doslo je leto i pocele su nove akcije Volonterskog kampa.<br>

Milena i Mister S su dobili zaduzenje da prociste kanale za navodnjavanje iz kojih se napajaju vidre (verovali ili ne). Mreza se sastoji od jednog kanala kojim se dovodi voda (zvacemo ga kanal A), jednog kanala kojim se odvodi voda (zvacemo ga kanal B) i spleta kanala koji nose vodu od A do B. Svaki kanal ima odredjenu dubinu i potreban je stap bar iste duzine (ili duzi) da bi se kanal procistio. Kroz svaki kanal prolazi isti kapacitet vode. Posto je tesko naci dugacke stapove, Milenu i Mistera S zanima koji je najkraci stap koji je potrebno da koriste tako da kad ociste kanale sa ne vecom dubinom nego duzina stapa, kolicina vode koja prodje od A do B bude maximalna.
Normalno je da se kanali spajaju. Oni se spajaju u tackama koje ce biti date. Jedan kraj jednog kanala ce biti povezan samo u jednoj tacki. Kanal A i kanal B nece biti povezani u istoj tacki. Jedino ce kanali A i B sadrzati svoje krajeve u vise tacaka (veliki su i imaju puno rukavaca). Kroz svaku tacku u kojoj se spajaju kanali, moze da prodje tacno ista kolicina vode kao i kroz svaki kanal pojedinacno (jedinicna kolicina).
<br><br>


Ulaz:<br><br>

U prvom redu ce biti dat broj kanala <i>n</i> (1 <= <i>n</i> <= 200) (bez kanala A i B) i broj tacaka <i>m</i> (2 <= <i>m</i> <= 2 * <i>n</i>)
U narednih <i>n</i> redova se ucitavaju po tri broja <i>d</i> (1 <= <i>d</i> <= 10000), <i>a</i> (1 <= <i>a</i> <= m), <i>b</i> (1 <= <i>b</i> <= m), redom za kanale od 1 do n, gde <i>d</i> predstavlja dubinu kanala, a <i>a</i> i <i>b</i> tacke koje kanal spaja (<i>a</i> je uvek razlicito od <i>b</i>).

<br><br>
Nakon toga se u naredna dva reda (prvi red za kanal A, a drugi za kanal B) ucitava broj <i>c</i> i u istom redu <i>c</i> brojeva, koji znace u kojim tackama se nalazi rukavci tog kanala.

<br><br>

NAPOMENA: Kanale A i B nema potrebe cistiti i za njih nije data dubima. Iz kanala A voda samo otice, a u kanala B voda se samo uliva.

<br><br>
Izlaz:<br><br>
Na standardni izlaz, ispisati najkraci stap koji je potrebno koristiti da kolicina voda koja prodje od A do B bude maximalna moguca.
<br><br>

<br><br>
Primer:<br><br>

Ulaz:<br>
3 5<br>
5481 1 4<br>
8019 5 2<br>
6002 2 1<br>
1 4<br>
1 5<br>
<br>

<br>Izlaz:<br>
8019<br><br>


primer2:<br><br>
Ulaz:<br>
11 22<br>
668 18 22<br>
998 9 16<br>
1556 18 6<br>
7309 5 15<br>
7338 15 4<br>
8602 11 2<br>
4280 6 5<br>
2513 11 5<br>
8425 4 3<br>
1974 2 21<br>
1104 18 17<br>
2 3 7<br>
12 1 4 8 10 12 13 14 15 16 18 20 22<br>
<br>

Izlaz:<br>
8425<br><br>

primer3:<br>
4 5<br>
5 1 3<br>
10 2 3<br>
5 3 4<br>
10 3 5<br>
2 1 2<br>
2 4 5<br><br>

Izlaz:<br>
5<br><br>

Napomena: Resenje je da prodje voda od kanala A, pa prvim kanalom, pa
trecim i onda u B. Ne moze vise vode da prodje jer SVAKI DEO sistema
sem kanala A i B moze da primi najvise jedinicu kolicinu, pa takodje i
u tackama u kojima se spajaju.