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)\)

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(2\le n,q\le 20\)

• Subtask \(2\) (\(80\%\) số điểm): Không có điều kiện gì

Example

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

4
1