📖 Bài giảng & lời giải: đây là Bài tập 7 trong bài giảng Bài 47: Heavy-Light Decomposition trên blog Lập trình thuật toán – có lý thuyết, mô phỏng từng bước, gợi ý và code C++ / Python.

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới xem gợi ý và lời giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Một vùng núi có $n$ trạm, đánh số $1..n$, và $m$ con đường hai chiều; con đường thứ $i$ nối hai trạm $u_i, v_i$ và có độ dốc $w_i$. Dữ liệu đảm bảo từ một trạm bất kỳ có thể đi tới mọi trạm khác.

Độ khó của một hành trình là độ dốc lớn nhất trong các con đường mà hành trình đi qua. Có $q$ truy vấn, mỗi truy vấn cho hai trạm $u, v$: hãy in ra độ khó nhỏ nhất có thể của một hành trình đi từ $u$ tới $v$ (in $0$ nếu $u = v$).

Dữ liệu vào

• Dòng 1: ba số nguyên $n, m, q$ ($1 \le n \le 10^5$, $n - 1 \le m \le 2 \cdot 10^5$, $1 \le q \le 10^5$).
• $m$ dòng tiếp theo, mỗi dòng gồm ba số nguyên $u_i, v_i, w_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$, $1 \le w_i \le 10^9$). Có thể có nhiều con đường nối cùng một cặp trạm.
• $q$ dòng tiếp theo, mỗi dòng gồm hai số nguyên $u, v$ ($1 \le u, v \le n$).

Kết quả

Với mỗi truy vấn, in kết quả trên một dòng.

Sample Input

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

Sample Output

5
2
0