老虎和蒜头是好朋友。

老虎最近在研究树上路径问题。具体来说，老虎有一棵 $ n $ 个节点的树，树的边上有权值。老虎认为一条路径是好的，当且仅当这条路径上的所有边的权值的最大公约数恰好为 $ 1 $ 。

蒜头有 $ m $ 次询问，每次询问蒜头会给出一对点 $ (u, v) $ ，表示询问最小的 $ l $ ，使得所有同时经过点 $ u $ 和点 $ v $ 的长度至少为 $ l $ 的路径都是好的。如果不存在这样的 $ l $ ，输出 $ -1 $ 。

你能帮蒜头解决这个问题吗？

输入格式

输入的第一行包括两个正整数 $ n, m $ ，表示树上的点数和询问的数目。

接下来 $ n - 1 $ 行，每行三个正整数 $ u_i, v_i, c_i $，表示一条权值为 $ c $ 的路径。

接下来 $ m $ 行，每行两个正整数 $ u, v $，表示一次询问。

输出格式

对每组询问，输出一行一个 $ l $ 。

样例一

input

12 5
4 1 4
4 3 6
1 6 2
1 5 8
3 2 12
6 10 3
5 7 10
2 8 3
2 11 4
11 9 5
3 12 15
8 12
1 10
1 2
3 8
3 6

output

-1
2
7
4
6

限制与约定

本题共包括 5 个子任务，对于所有子任务，均有 $ 1 \le c \le 10^6, u \ne v $ 。

Subtask 1(19 分): $ 1 \le n \le 3 \times 10^5, u_i = i, v_i = i + 1 $

Subtask 2(21 分): $ 1 \le n \le 3 \times 10^5, c_i \le 2 $

Subtask 3(11 分): $ 1 \le n, m \le 2000 $

Subtask 4(33 分): $ 1 \le n, m \le 10^5 $

Subtask 5(16 分): $ 1 \le n, m \le 3 \times 10^5 $

时间限制: 4s

空间限制: 512MB