F. Дороги и рамен
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В стране Огня есть $$$n$$$ деревень и $$$n-1$$$ двусторонняя дорога, причем из каждой деревни можно добраться в каждую по дорогам. В этой стране есть только два типа дорог: каменные и песчаные. Поскольку страна Огня очень прогрессивная и постоянно обновляется, то каждый день рано утром строители выбирают одну дорогу и меняют ее тип (с каменной на песчаную или наоборот). А еще в стране Огня все любят рамен, поэтому каждый день на каждой каменной дороге устанавливается одна палатка с раменом, а в конце дня палатку убирают.

В течение каждого из ближайших $$$m$$$ дней, после того как очередную дорогу переделают, Наруто и Джирайя выбирают себе простой маршрут по стране Огня. Их маршрут может начинаться с любой деревни и заканчиваться тоже в любой (возможно, той же), но по каждой дороге они могут проходить не более одного раза. Поскольку Наруто и Джирайя очень любят рамен, то на каждой каменной дороге они обязательно покупают ровно одну тарелку рамена и кто-нибудь один из них ее ест. Поскольку у ниндзя все должно быть честно, то они выбирают только те пути, проходя по которым они могут съесть равное количество тарелок с раменом. Наруто и Джирайя любят много путешествовать, поэтому каждый день они выбирают самый длинный путь из подходящих. Для каждого дня необходимо определить максимальную длину пути (то есть количество дорог в нём), которым могут пойти Наруто и Джирайя.

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

В первой строке дано натуральное число $$$n$$$ ($$$2 \leq n \leq 500\,000$$$) — число деревень в стране Огня.

Каждая из следующей $$$(n-1)$$$ строки содержит описание дороги: три натуральных числа $$$u$$$, $$$v$$$ и $$$t$$$ ($$$1 \leq u, v \leq n$$$, $$$t \in \{0,1\}$$$). Первые два числа определяют номера деревень, между которыми проложена дорога, а третье число определяет начальный тип дороги: $$$0$$$ — песчаная, $$$1$$$ — каменная. Дороги нумеруются числами от $$$1$$$ до $$$(n-1)$$$ в порядке, заданном во входных данных.

В следующей строке задано натуральное число $$$m$$$ ($$$1 \leq m \leq 500\,000$$$) — число дней, которые путешествуют Наруто и Джирайя.

Каждая из последующих $$$m$$$ строк содержит одно число $$$id$$$ ($$$1 \leq id \leq n-1$$$) — номер дороги, которую переделывают утром соответствующего дня.

Гарантируется, что между любыми двумя деревнями есть путь по дорогам.

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

Необходимо вывести $$$m$$$ строк, $$$i$$$-я из которых содержит максимальную длину подходящего пути в $$$i$$$-й день.

Пример
Входные данные
5
1 2 0
1 3 0
3 5 0
3 4 0
5
3
4
1
3
4
Выходные данные
3
2
3
3
2
Примечание

После изменения дороги под номером $$$3$$$ самый длинный путь состоит из дорог $$$1$$$, $$$2$$$ и $$$4$$$.

После изменения дороги под номером $$$4$$$ самый длинный путь может состоять из дорог $$$1$$$ и $$$2$$$.

После изменения дороги под номером $$$1$$$ самый длинный путь может состоять из дорог $$$1$$$, $$$2$$$ и $$$3$$$.

После изменения дороги под номером $$$3$$$ самый длинный путь состоит из дорог $$$1$$$, $$$2$$$ и $$$4$$$.

После изменения дороги под номером $$$4$$$ самый длинный путь может состоять из дорог $$$2$$$ и $$$4$$$.