Задача №115448. Разноцветный граф
Недавно Матвей на уроках информатики изучил графы. Граф представляет собой \(n\) вершин, некоторые из которых могут соединяться ребрами. Матвей — художник, и ему очень нравится рисовать. Когда он рисует граф, он изображает его ребра разными цветами. Будем обозначать цвета натуральными числами от \(1\) до \(10^5\).
Матвей придумал себе следующую задачу. Исходно в графе \(n\) вершин и нет ребер, а затем выполняется \(q\) запросов.
- \(+\) \(v\) \(u\) \(c\) — добавить в граф ребро \((v, u)\) цвета \(c\). Гарантируется, что ребра цвета \(c\) между вершинами \(v\) и \(u\) не было.
- \(-\) \(v\) \(u\) \(c\) — удалить в графе ребро \((v, u)\) цвета \(c\). Гарантируется, что ребро такого цвета было между вершинами \(u\) и \(v\).
Так как Матвей — художник, он считает, что цвет \(c\) в графе является превосходным , если с каждой вершиной соединено не более одного ребра этого цвета. Определим красоту цвета \(c\) как количество рёбер такого цвета.
После каждого запроса ему стало интересно, какую суммарную красоту имеет граф по всем превосходным цветам.
В первой строке даны два целых числа \(n\) и \(q\) — количество вершин в графе и количество запросов, соответственно (\(2 \le n \le 10^5\), \(1 \le q \le 10^5\)).
В последующих \(q\) строках даны описания запросов, по одному в строке (\(1 \le v, u \le n\); \(v \neq u\); \(1 \le c \le 10^5\)).
После каждого запроса вам нужно вывести суммарную красоту графа по всем превосходным цветам.
В первом примере после первого запроса все цвета являются превосходными.
После второго запроса все цвета являются превосходными.
После третьего запроса цвет 1 не является превосходным, так как из вершины 2 исходит два ребра цвета 1. Цвет 2 является превосходным, и в графе есть одно ребро такого цвета.
После четвертого запроса все цвета являются превосходными.
После пятого запроса все цвета являются превосходными.
4 5 + 1 2 1 + 3 4 2 + 2 4 1 - 2 1 1 + 2 4 4
1 2 1 2 3
3 6 + 1 2 1 + 2 3 1 + 1 3 1 - 1 3 1 - 1 2 1 + 1 2 1
1 0 0 0 1 0