Cho đồ thị vô hướng, liên thông, có trọng số gồm ~n~ đỉnh và ~n-1~ cạnh. Gọi ~f~ là khoảng cách xa nhất giữa ~2~ đỉnh trong ~n~ đỉnh đã cho.

Bây giờ, ta có ~q~ truy vấn, mỗi truy vấn gồm ~2~ số ~u\text{ }v~ - Thể hiện cạnh thứ ~u~ và cạnh thứ ~v~ của đồ thị đã cho. (~u\ne v~) (Biết rằng, các cạnh của đồ thị được đánh số bắt đầu từ ~1~).

Yêu cầu: Ứng với mỗi truy vấn, in ra ~f~ nếu giả sử rằng: Đồ thị đã cho bị mất đi hai cạnh ~u~ và ~v~

Input:

• Dòng thứ nhất chứa hai số nguyên ~n,q(1\le n,q\le 10^5)~

• ~n-1~ dòng tiếp theo, mỗi dòng gồm ~3~ số nguyên ~x,y,z~ - Thể hiện cạnh được nối bởi đỉnh ~x~ và đỉnh ~y~ có trọng số là ~z(0\le z\le 5000)~

• ~q~ dòng tiếp theo, mỗi dòng gồm ~2~ số nguyên ~u,v(1\le u,v\le n-1 ; u\ne v)~

Ví dụ:

Input:

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

Output:

~ 4 1 ~

Giải thích:

Subtask:

• ~20\text{%}~ : ~2\le n,q\le 20~

• ~80\text{%}%~ : Không có điều kiện gì