Задано реберно-взвешенное дерево из \(n\) вершин, каждое ребро которого окрашено в некоторый цвет. Каждая вершина дерева может быть заблокирована или разблокирована. Изначально все вершины разблокированы.
Простой путь — это путь в графе, который не имеет повторяющихся вершин. Длина пути определяется как сумма весов всех ребер на пути.
Путь называется хорошим, если это простой путь, состоящий из ребер одного цвета \(c\), все ребра цвета \(c\) в дереве лежат на этом пути, и каждая вершина пути разблокирована.
Вам нужно обрабатывать запросы \(2\)-х типов:
- заблокировать вершину,
- разблокировать вершину.
После каждого запроса выведите максимальную длину среди всех хороших путей. Если не существует хорошего пути, выведите \(0\).
Выходные данные
Для каждого запроса выведите максимальную длину хорошего пути. Если не существует хорошего пути, выведите \(0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 4
4 1 3 4
5 2 4 4
3 1 3 2
1 2 5 1
0 4
0 3
0 2
1 3
|
5
5
0
3
|
|
2
|
5 5
4 1 4 4
4 5 2 2
3 1 2 4
3 2 3 1
0 3
0 4
1 3
1 4
0 1
|
2
0
3
6
3
|
|
3
|
6 9
3 2 2 3
2 4 4 2
3 1 5 5
6 4 3 2
5 3 1 3
0 2
0 4
0 5
0 6
1 2
1 4
1 5
0 3
1 6
|
5
5
5
5
5
5
5
0
7
|
|
4
|
1 2
0 1
1 1
|
0
0
|