Задано реберно-взвешенное дерево из $$$n$$$ вершин, каждое ребро которого окрашено в некоторый цвет. Каждая вершина дерева может быть заблокирована или разблокирована. Изначально все вершины разблокированы.
Простой путь — это путь в графе, который не имеет повторяющихся вершин. Длина пути определяется как сумма весов всех ребер на пути.
Путь называется хорошим, если это простой путь, состоящий из ребер одного цвета $$$c$$$, все ребра цвета $$$c$$$ в дереве лежат на этом пути, и каждая вершина пути разблокирована.
Вам нужно обрабатывать запросы $$$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$$$), обозначающие запрос:
Для каждого запроса выведите максимальную длину хорошего пути. Если не существует хорошего пути, выведите $$$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
