Cho cây gồm ~n~ đỉnh. Mỗi cạnh ~u, v~ có những màu sắc khác nhau. hieuhfgr cho bạn ~q~ truy vấn, mỗi truy vấn có hai đỉnh ~u, v, x~, nhiệm vụ của bạn là tìm một lộ trình đi từ đỉnh ~u~ đến đỉnh ~v~ sao cho trên lộ trình đó là ngắn nhất và tồn tại cạnh có màu sắc là ~x~

Input

Dòng đầu là ~n~ và ~q~ tương ứng số đỉnh của cây và số truy vấn.

~n - 1~ dòng tiếp theo, mỗi dòng là ~u~ ~v~ ~c~ tượng trưng cho có cạnh nối hai đỉnh ~u~ và ~v~ và có màu là ~c~.

~q~ dòng cuối cùng gồm ~u~ ~v~ ~x~ hỏi như yêu cầu đề bài.

Output

Với mối truy vấn in ra số cạnh ít nhất để có lộ trình như đề yêu cầu. Nếu không thể tạo ra lộ trình thì in ra ~-1~

Constraints

• ~n \le 1000~
• ~q \le 200000~
• ~c \le 10^9~

Sample Input

9 5
1 2 1
2 3 2
1 4 3 
1 5 1
5 6 3
6 7 4
6 8 1
8 9 4
3 9 1
3 9 5
2 1 4
4 5 2
1 5 4

Sample Output

6
-1
7
6
5

Note

• với truy vấn ~(3, 9, 1)~, lộ trình ngắn nhất là: ~3, 2, 1, 5, 6, 8, 9~ nên đáp án là ~6~.
• với truy vấn ~(3, 9, 5)~, không tồn tại lộ trình mà trong đó có cạnh có màu sắc là ~5~.
• với truy vấn ~(2, 1, 4)~, lộ trình ngắn nhất là: ~2, 1, 5, 6, 7, 6, 5, 1~. nên đáp án là ~7~