Поток в меняющейся сети
Поток в меняющейся сети
Задана ориентированная сеть, с которой производят два вида операций. Первая операция увеличивает на 1 пропускную способность ребра из x в y, а вторая операция уменьшает на 1 пропускную способность ребра из x в y.
Ваша задача выводить значение максимального потока в сети из вершины 1 в вершину n после каждой из операций.
Входные данные
В первой строке записаны целые числа n, m (2 ≤ n ≤ 150, 0 ≤ m ≤ 2000), где n — это количество вершин в сети, а m — количество рёбер. Далее в m строках перечислены сами рёбра (x, y) с пропускной способностью c по одному в строке тройками чисел x, y, c (1 ≤ x, y ≤ n, 1 ≤ c ≤ 1000). Далее входные данные содержат число t (1 ≤ t ≤ 500), где t — количество операций производимых над сетью. Затем t строк содержат каждую из операций. Операции задаются последовательностями "1 x y" и "2 x y" в зависимости от типа.
Сеть в любой момент времени не содержит кратных рёбер и петель. Пропускная способность любого ребра в сети в любой момент времени — неотрицательна.
Выходные данные
Выведите t+1 число. В качестве первого числа выведите значение максимального потока в заданной сети до произведения всех операций. Далее выведите t чисел — значения максимального потока после каждой операции.
Пример
4 5 1 2 15 2 3 5 3 4 15 1 3 5 2 4 5 2 1 2 3 2 1 3
15 16 15