Дан неориентированный взвешенный граф, состоящий из \(n\) вершин и \(m\) рёбер.
На этом графе осуществляются запросы:
- Удалить из графа существующее ребро.
- Добавить в граф ещё не существующее в нём ребро.
В самом начале и после каждого запроса вам необходимо найти четыре различные вершины \(a\), \(b\), \(c\), \(d\) такие, что существует путь между \(a\) и \(b\), существует путь между \(c\) и \(d\) и сумма длин двух кратчайших путей из \(a\) в \(b\) и из \(c\) в \(d\) минимальна. Ответ на запрос — это сумма длин этих двух кратчайших путей. Длина пути равна сумме весов рёбер на этом пути.
Выходные данные
Выведите \(q + 1\) целое число — минимальную сумму длин кратчайших путей для выбранных пар вершин до всех запросов и после каждого из них.
Примечание
До всех запросов можно выбрать вершины \((a, b) = (3, 2)\) и \((c, d) = (1, 4)\). Сумма длин двух кратчайших путей равна \(3 + 1 = 4\).
После первого запроса можно выбрать вершины \((a, b) = (2, 5)\) и \((c, d) = (1, 4)\). Сумма длин двух кратчайших путей равна \(2 + 1 = 3\).
После второго запроса можно выбрать вершины \((a, b) = (3, 4)\) и \((c, d) = (2, 5)\). Сумма длин двух кратчайших путей равна \(1 + 2 = 3\).
После третьего запроса можно выбрать вершины \((a, b) = (2, 6)\) и \((c, d) = (4, 5)\). Сумма длин двух кратчайших путей равна \(4 + 3 = 7\).
После последнего запроса можно выбрать вершины \((a, b) = (1, 6)\) и \((c, d) = (2, 5)\). Сумма длин двух кратчайших путей равна \(3 + 2 = 5\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 6
1 3 6
4 3 1
1 4 1
2 6 4
2 4 2
5 4 3
4
1 2 5 2
0 1 4
0 3 4
1 6 1 3
|
4
3
3
7
5
|