火之国中有 $$$n$$$ 个村庄和 $$$n-1$$$ 双向道路,并且任何一对村庄之间都有一条道路。道路只有两种:石路和沙路。由于火之国在不断翻新,每天早上工人们都会选择一条道路并翻转其类型(因此,如果是沙路,则变成石路,反之亦然)。而且这里的每个人都喜欢拉面,所以每天早上,每条石路中间都会设置一个拉面亭,每天结束时,所有的亭子都会被拆除。
对于接下来的每一天,在另一条路被翻转后,鸣人和自来也都会选择一条简单的路径——也就是说,一条从一个村庄开始到另一个(可能是同一个)村庄结束的路线,并且不包含任何道路两次。由于鸣人和自来也也非常喜欢拉面,所以他们在每条石路上买了一杯拉面,一人吃。由于不想得罪对方,所以他们只选择能吃到同等杯数拉面的路线。由于他们都喜欢旅行,所以他们会选择尽可能最长的路径。每次改造后,找出他们可以遵循的最大可能路径长度(即其中的道路数量)。
输入
第一行包含唯一的正整数 $$$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$$$ 天任何有效路径的最大可能长度。
示例
输入 #1
5 1 2 0 1 3 0 3 5 0 3 4 0 5 3 4 1 3 4
输出 #1
3 2 3 3 2
注意
$$$3$$$-rd 道路改造后,最长的路径由道路 $$$1$$$、$$$2$$$ 和 $$$4$$$ 组成。
第 $$$4$$$ 条道路改造后,最长的路径之一由道路 $$$1$$$ 和 $$$2$$$ 组成。
$$$1$$$-st 道路整修后,最长的路径之一由道路 $$$1$$$、$$$2$$$ 和 $$$3$$$ 组成。
$$$3$$$-rd 道路改造后,最长的路径由道路 $$$1$$$、$$$2$$$ 和 $$$4$$$ 组成。
$$$4$$$-rd 路改造后,最长的路径之一由 $$$2$$$ 和 $$$4$$$ 路组成。