Tý cần giải bài toán sau:

Cạnh lớn nhất

Định dạng đầu vào

• Dòng đầu chứa số nguyên \(N\) và \(Q\) (\(N, Q \le 10^5\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) mô tả một cạnh.

Định dạng đầu ra

• In ra kết quả của từng truy vấn trên một dòng.

Ví dụ

Input:

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

Output:

3

Trong một khu rừng già FPTOJ có \(N\) cái cây cổ thụ, giữa chúng được nối với nhau bởi \(N-1\) sợi dây leo. Mỗi sợi dây leo có một độ bền nhất định (là số nguyên dương). Một nhà thám hiểm muốn đi từ cây \(u\) sang cây \(v\) bằng cách bám vào các sợi dây leo. Anh ta chỉ có thể mang theo một lượng hành lý nhất định, và lượng hành lý tối đa mà anh ta có thể mang khi đi qua một tuyến đường bằng độ bền nhỏ nhất của các sợi dây trên tuyến đường đó. Với mỗi hành trình, hãy giúp nhà thám hiểm biết sợi dây yếu nhất (có độ bền nhỏ nhất) trên đường đi là bao nhiêu.

Yêu cầu: Cho \(N\) cây và \(N-1\) sợi dây leo. Trả lời \(Q\) truy vấn, mỗi truy vấn yêu cầu in ra giá trị nhỏ nhất của các cạnh trên đường đi từ \(u\) đến \(v\).

Dữ liệu vào:

• Dòng đầu chứa số nguyên dương \(N\).
• \(N-1\) dòng tiếp theo, mỗi dòng gồm ba số \(u\), \(v\), \(w\) cho biết sợi dây nối cây \(u\) và cây \(v\) có độ bền \(w\).
• Dòng tiếp theo chứa số nguyên dương \(Q\).
• \(Q\) dòng sau, mỗi dòng gồm hai số \(u\), \(v\) là truy vấn.

Kết quả:

• In ra \(Q\) dòng, mỗi dòng là giá trị nhỏ nhất của các cạnh trên đường đi tương ứng.

Ví dụ:

Dữ liệu vào:

5
1 2 3
1 3 5
2 4 2
2 5 7
3
4 3
4 5
1 4

Kết quả:

2
2
2

Giải thích:

• Đường đi \(4 \to 2 \to 1 \to 3\) có các cạnh \(\{2, 3, 5\}\), sợi yếu nhất là \(2\).
• Đường đi \(4 \to 2 \to 5\) có các cạnh \(\{2, 7\}\), sợi yếu nhất là \(2\).
• Đường đi \(1 \to 2 \to 4\) có các cạnh \(\{3, 2\}\), sợi yếu nhất là \(2\).

Giới hạn: | Subtask | \(N\) | \(Q\) | Điểm | |---------|-----|-----|------| | 1 | ≤ 100 | ≤ 100 | 5 | | 2 | ≤ 500 | ≤ 500 | 5 | | 3 | ≤ 2 000 | ≤ 2 000 | 10 | | 4 | ≤ 10 000 | ≤ 10 000 | 10 | | 5 | ≤ 50 000 | ≤ 50 000 | 15 | | 6 | ≤ 100 000 | ≤ 100 000 | 15 | | 7 | ≤ 100 000 | ≤ 100 000 | 20 | | 8 | ≤ 100 000 | ≤ 100 000 | 20 |