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

Cạnh nhỏ 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

Vương quốc FPTOJ có \(N\) thành phố được kết nối với nhau bởi \(N-1\) con đường, tạo thành một mạng lưới liên thông. Mỗi con đường có một độ khó đi qua (là một số nguyên dương). Hoàng tử của vương quốc muốn đi thăm các thành phố, nhưng chàng chỉ muốn đi qua những con đường dễ đi nhất có thể. Với mỗi hành trình từ thành phố \(u\) đến thành phố \(v\), chàng muốn biết con đường dễ đi nhất (có độ khó nhỏ nhất) trên đường đi là bao nhiêu.

Yêu cầu: Cho \(N\) thành phố và \(N-1\) con đường. Trả lời \(Q\) truy vấn, mỗi truy vấn yêu cầu in ra giá trị nhỏ nhất trong 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 có con đường nối hai thành phố \(u\) và \(v\) với độ khó \(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\}\), giá trị nhỏ nhất là \(2\).
• Đường đi \(4 \to 2 \to 5\) có các cạnh \(\{2, 7\}\), giá trị nhỏ nhất là \(2\).
• Đường đi \(1 \to 2 \to 4\) có các cạnh \(\{3, 2\}\), giá trị nhỏ 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 |