Вам дан взвешенный ориентированный граф, содержащий \(n\) вершин и \(m\) ребер. Каждая вершина графа может быть выделенной или обычной, изначально все вершины обычные. Ценой графа назовём минимальную суммарную цену рёбер, которые нужно взять, чтобы из каждой обычной вершины была достижима по взятым ребрам хотя бы одна любая выделенная вершина. Если такого набора рёбер не существует, то цена равна \(-1\).
Вам предстоит вычислить цену графа после каждого из \(q\) запросов. Запросы бывают двух типов:
- \(+\;v_i\) делает вершину \(v_i\) выделенной; гарантируется, что перед запросом вершина была обычной.
- \(-\;v_i\) делает вершину \(v_i\) обычной; гарантируется, что перед запросом вершина была выделенной.
Выведите цену графа после каждого из \(q\) запросов.
Выходные данные
Выведите \(q\) чисел. \(i\)-е число — это цена графа после первых \(i\) запросов.
Примечание
В первом тесте:
- Посыле первого запроса выгоднее всего взять ребра с номерами \(3, 4, 5\), сумма их цен равна \(15\).
- После второго запроса, нет ни одной выделенной вершины, а значит, не существует подходящих наборов ребер, цена графа \(-1\).
- После третьего запроса выгоднее всего взять ребра с номерами \(1, 2, 5\), сумма их цен равна \(14\).
- После четвертого запроса выгоднее всего взять ребра с номерами \(4\) и \(5\), сумма их цен равна \(12\).
- После пятого запроса выгоднее всего взять только ребро номер \(5\), его цена равна \(4\).
- После шестого запроса все вершины выделенные и можно не брать ребер, цена графа равна \(0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 5 6
1 2 1
2 3 5
3 2 3
4 1 8
2 1 4
+ 1
- 1
+ 3
+ 1
+ 4
+ 2
|
15
-1
14
12
4
0
|
|
2
|
10 14 10
8 6 4
2 5 1
3 5 4
1 6 3
1 3 7
7 2 1
6 1 3
4 10 1
4 6 5
5 4 1
5 8 10
10 9 1
9 5 1
9 7 6
+ 7
+ 8
- 7
+ 10
+ 2
- 10
+ 5
- 2
- 5
+ 3
|
28
24
29
19
18
24
18
19
29
20
|