Задачі
Потік у мінливій мережі
Потік у мінливій мережі
Задано орієнтовну мережуь, з якою проиводять два види операцій. Перша операція збільшує на \textbf{1 }пропускну здатність ребра з \textbf{x} в \textbf{y}, а друга операція зменшує на \textbf{1} пропускну здатність ребра з \textbf{x} в \textbf{y}.
Ваша задача виводити значення максимального потоку у мережі з вершини \textbf{1} у вершину \textbf{n} після кожної з операцій.
\InputFile
У першому рядку записано цілі числа \textbf{n}, \textbf{m} (\textbf{2} ≤ \textbf{n} ≤ \textbf{150}, \textbf{0} ≤ \textbf{m} ≤ \textbf{2000}), де \textbf{n} --- це кількість вершин у мережі, а \textbf{m} --- кількість ребер. Далі у \textbf{m} рядках перераховано самі ребра (\textbf{x}, \textbf{y}) з пропускною здатністю \textbf{c} по одному у рядку трійками чисел \textbf{x}, \textbf{y}, \textbf{c} (\textbf{1} ≤ \textbf{x}, \textbf{y} ≤ \textbf{n}, \textbf{1} ≤ \textbf{c} ≤ \textbf{1000}). Далі вхідні дані містят число \textbf{t} (\textbf{1} ≤ \textbf{t} ≤ \textbf{500}), де \textbf{t} --- кількість операцій, що виконуються над мережою. Потім \textbf{t} рядків містять кожну з операцій. Операції задаються послідовностями "\textbf{1 x y}" та "\textbf{2 x y}" у залежності від типу.
Мережа у довільний момент часу не містить кратних ребер та петель. Пропускна здатність довільного ребра у мережі у довільний момент часу --- невід'ємна.
\OutputFile
Виведіть \textbf{t+1} число. У якості першого числа виведіть значення максимального потоку у заданій мережі до проведення усіх операцій. Далі виведіть \textbf{t} чисел --- значення максимального потоку після кожної операції.
Вхідні дані #1
4 5 1 2 15 2 3 5 3 4 15 1 3 5 2 4 5 2 1 2 3 2 1 3
Вихідні дані #1
15 16 15