Şəbəkədə dəyişən axın#4589
Verilmiş istiqamətli şəbəkə üzrə iki növ əməliyyat aparmaq mümkündür. Birinci əməliyyat -dən -yə olan qırağın tutumunu vahid artırır, ikinci əməliyyat isə -dən -yə olan qırağın tutumunu vahid azaldır.
Sizin vəzifəniz hər bir əməliyyatdan sonra, şəbəkədə -ci zirvədən -ci zirvəyə olan maksimal axının qiymətini çap etməkdir.
Birinci sətirdə iki tam ədəd və (2 \leq n \leq 150, 0 \leq m \leq 2000) verilib, burada - şəbəkədəki zirvələrin sayı, isə qıraqların sayıdır. Növbəti sətirdə qıraqlar təsvir olunur: hər sətirdə üç tam ədəd , , (1 \leq x, y \leq n, 1 \leq c \leq 1000) verilir, yəni -dən -yə istiqamətli qıraq və onun tutumu .
Sonrakı sətirdə bir tam ədəd (1 \leq t \leq 500), yəni əməliyyatların sayı verilir. Onun ardınca növbəti sətirdə əməliyyatlar verilir, hər biri "1 x y" və ya "2 x y" kimi qeyd olunmuşdur, asılı olaraq əməliyyatın növündən.
Heç bir anda şəbəkədə eyni zirvə cütü arasında çoxlu qıraq və ya özünə qıraq (self-loop) olmur. Hər bir qırağın tutumu heç vaxt mənfi olmur.
t+1 ədəd çap edin. Əvvəlcə, heç bir əməliyyat aparılmamışdan əvvəl şəbəkədə maksimal axının qiymətini çıxışa verin. Daha sonra isə, hər bir əməliyyatdan sonra cari şəbəkədə maksimal axının qiymətini çıxışa verin.
Nümunə 1