Laiko ribojimas: 1s

Atminties ribojimas: 1024MB

Duomenų failas: 2018_stovykla_vyr_srautai.in

Rezultatų failas: 2018_stovykla_vyr_srautai.out

Jei norite pateikti savo sprendimą - prisijunkite.

Srautai

Jums duotas jungus bekryptinis svorinis grafas G. Šį grafą sudaro N viršūnių (sunumeruotuo skaičiais 1,2,3,\\ldots,N) ir M briaunų (sunumeruotų skaičiais 1,2,3,\\ldots,M).

Šis grafas yra paprastas, kadangi:

  • Tarp bet kurių dviejų viršūnių eina ne daugiau kaip viena briauna (nėra multibriaunų);
  • Jokia briauna nejungia viršūnės su ja pačia (nėra kilpų);
  • Jokia viršūnė nepriklauso daugiau nei vienam ciklui.

Užduotis

Jums reikia parašyti programą, kuri, turint pradinį grafą G, sugebėtų atsakyti į užklausas:

  • 0 i j -- nulinio tipo užklausa, kurią gavusi programa turi atspausdinti maksimalų srautą tarp viršūnių 1\\leqi\\nej\\leqN.
  • 1 i c -- pirmo tipo užklausa, kurią gavusi programa turi pakeisti 1\\leq i'tosios \\leqM briaunos svorį į 1\\leqc\\leq1000000000.

Pradiniai duomenys

Pirmoje eilutėje pateikti du skaičiai 1\\leqN\\leq100000,0\\leqM\\leq200000.

Toliau pateikta M eilučių, kiekvienoje iš jų aprašoma viena briauna. Briauna aprašoma trimis skaiciai 1\\leqv_i\\leqN,1\\leqw_i\\leqN,1\\leqc_i\\leq1000000000 nurodančiai, kad c_i svorio briauna jungia virūnę v_i su w_i.

Galiausiai pateikiamas užklausų skaičius 0\\leqQ\\leq200000

Rezultatai

Jums reikės išvesti atsakymus į pateiktas užklausas.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
5 5
1 2 1
2 3 2
3 4 3
4 5 4
5 1 5
3
0 1 5
1 1 2
0 1 5
 
6
7