G. Раскраска дерева
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задано реберно-взвешенное дерево из $$$n$$$ вершин, каждое ребро которого окрашено в некоторый цвет. Каждая вершина дерева может быть заблокирована или разблокирована. Изначально все вершины разблокированы.

Простой путь — это путь в графе, который не имеет повторяющихся вершин. Длина пути определяется как сумма весов всех ребер на пути.

Путь называется хорошим, если это простой путь, состоящий из ребер одного цвета $$$c$$$, все ребра цвета $$$c$$$ в дереве лежат на этом пути, и каждая вершина пути разблокирована.

Вам нужно обрабатывать запросы $$$2$$$-х типов:

  1. заблокировать вершину,
  2. разблокировать вершину.

После каждого запроса выведите максимальную длину среди всех хороших путей. Если не существует хорошего пути, выведите $$$0$$$.

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

Первая строка содержит два целых числа $$$n$$$, $$$q$$$ ($$$1 \leq n,q \leq 2\cdot 10^5$$$) — количество вершин и количество запросов.

Затем следуют $$$n-1$$$ строка, каждая из которых содержит четыре целых числа $$$u$$$, $$$v$$$, $$$w$$$ и $$$c$$$ ($$$1 \leq u,v,w,c \leq n$$$; $$$u \not = v$$$), обозначающие взвешенное ребро, соединяющее вершины $$$u$$$ и $$$v$$$ с весом $$$w$$$ и цветом $$$c$$$. Гарантируется, что эти ребра образуют дерево.

Затем следуют $$$q$$$ строк, каждая из которых содержит два целых числа $$$p$$$ и $$$x$$$ ($$$p = 0$$$ или $$$p = 1$$$, $$$1\leq x\leq n$$$), обозначающие запрос:

  1. Если $$$p = 0$$$, заблокируйте вершину $$$x$$$. Гарантируется, что она не заблокирована в это время.
  2. Если $$$p = 1$$$, разблокируйте вершину $$$x$$$. Гарантируется, что она заблокирована в это время.
Выходные данные

Для каждого запроса выведите максимальную длину хорошего пути. Если не существует хорошего пути, выведите $$$0$$$.

Примеры
Входные данные
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
Входные данные
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
Входные данные
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
Входные данные
1 2
0 1
1 1
Выходные данные
0
0