📖 Bài giảng & lời giải: đây là Bài tập 6 trong bài giảng Bài 34: LCA, nhảy nhị phân 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ạng giao thông có $n$ thành phố đánh số từ $1$ tới $n$ và $m$ con đường hai chiều, con đường thứ $i$ nối hai thành phố khác nhau $u_i, v_i$ và có độ nguy hiểm $w_i$. Giữa hai thành phố có thể có nhiều con đường. Đảm bảo từ mỗi thành phố đều đi được tới mọi thành phố khác.

Độ nguy hiểm của một lộ trình là độ nguy hiểm lớn nhất của các con đường trên lộ trình đó. Có $q$ câu hỏi, mỗi câu cho hai thành phố $u, v$: đi từ $u$ tới $v$ thì độ nguy hiểm nhỏ nhất có thể của lộ trình là bao nhiêu? Nếu $u = v$ thì in $0$.

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 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, v, w$ ($1 \le u, v \le n$, $u \ne v$, $1 \le w \le 10^9$).
• $q$ dòng tiếp theo, mỗi dòng gồm hai số nguyên $u, v$ ($1 \le u, v \le n$, có thể $u = v$).

Kết quả

In $q$ dòng, dòng thứ $j$ là độ nguy hiểm nhỏ nhất của lộ trình cho câu hỏi thứ $j$.

Sample Input

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

Sample Output

2
5
5
3
0