eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Поток в меняющейся сети

Поток в меняющейся сети

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Задана ориентированная сеть, с которой производят два вида операций. Первая операция увеличивает на 1 пропускную способность ребра из x в y, а вторая операция уменьшает на 1 пропускную способность ребра из x в y.

Ваша задача выводить значение максимального потока в сети из вершины 1 в вершину n после каждой из операций.

Входные данные

В первой строке записаны целые числа n, m (2n150, 0m2000), где n — это количество вершин в сети, а m — количество рёбер. Далее в m строках перечислены сами рёбра (x, y) с пропускной способностью c по одному в строке тройками чисел x, y, c (1x, yn, 1c1000). Далее входные данные содержат число t (1t500), где t — количество операций производимых над сетью. Затем t строк содержат каждую из операций. Операции задаются последовательностями "1 x y" и "2 x y" в зависимости от типа.

Сеть в любой момент времени не содержит кратных рёбер и петель. Пропускная способность любого ребра в сети в любой момент времени — неотрицательна.

Выходные данные

Выведите t+1 число. В качестве первого числа выведите значение максимального потока в заданной сети до произведения всех операций. Далее выведите 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