给一棵树，边有颜色。

定义一条路径合法为：路径上的颜色只在这条路径上出现。

独立询问 $m$ 次，每次问删去一个点后仍然合法的路径的最大长度。

仍然合法定义为：在原树合法，且删去的点不在该路径上。

输入格式

第一行两个整数 $n,m$ 。

接下来 $n-1$ 行，每行三个整数 $x,y,col$, 表示树上有一条连接 $(x,y)$、颜色为 $col$ 的边。

接下来 $m$ 行，每行一个整数 $x$ 表示一组询问。

输出格式

$m$ 行，每行一个整数表示询问的答案。

样例数据

样例输入

4 4
1 2 2
1 3 1
1 4 1
1
2
3
4

样例输出

0
2
1
1

子任务

$m \le n \le 10^5, 1 \le x,y,col \le n$

子任务一（$9$ 分），$n \le 100$。

子任务二（$11$ 分），$n \le 1000$。

子任务三（$17$ 分），保证树的结构为一条链。

子任务四（$23$ 分），$m = 1$。

子任务五（$40$ 分），无特殊限制。