RC7-G. Avtobus balandligi

Viloyatda N ta qishloq va ularni ulaydigan M ta ikki tomonlama yo‘l bor. Har bir yo‘l temir yo‘l ko‘prigi ostidan o‘tadi: j-yo‘lning ko‘prigi ostidagi balandlik hⱼ santimetr — balandligi hⱼ dan oshmaydigan avtobus bu yo‘ldan o‘ta oladi. Ikki qishloq orasida bir nechta yo‘l bo‘lishi, yo‘l qishloqning o‘zidan o‘ziga qaytishi ham mumkin.

Litsey Q ta ekskursiya rejalashtirdi: k-ekskursiya aₖ qishloqdan bₖ qishloqqa borishi kerak, yo‘lni istalgancha tanlash mumkin. Har bir ekskursiya uchun shu ikki qishloq orasida yura oladigan eng baland avtobusning balandligini toping. Agar qishloqlar umuman ulanmagan bo‘lsa, -1 chiqaring.

Kirish ma’lumotlari

Birinchi qatorda uchta butun son N, M, Q.

Keyingi M qatorning har birida uchta butun son uⱼ, vⱼ, hⱼ — yo‘l uchlari va ko‘prik ostidagi balandlik.

Keyingi Q qatorning har birida ikkita butun son aₖ va bₖ — ekskursiya.

Chiqish ma’lumotlari

Har bir ekskursiya uchun alohida qatorda bitta butun son — eng baland avtobus balandligi yoki -1.

Cheklovlar

• 2 ≤ N ≤ 2·10⁵
• 0 ≤ M ≤ 2·10⁵, 1 ≤ Q ≤ 2·10⁵
• 1 ≤ uⱼ, vⱼ ≤ N, 1 ≤ hⱼ ≤ 10⁹
• 1 ≤ aₖ, bₖ ≤ N, aₖ ≠ bₖ

1-misol: 1 dan 3 ga to‘g‘ridan-to‘g‘ri yo‘l ko‘prigi 3 sm, lekin 1 → 2 → 3 yo‘lida ko‘priklar 4 va 6 — 4 sm li avtobus o‘tadi. 1 dan 4 ga: 1 → 2 → 3 → 4 (4, 6, 5) — javob 4. 2 dan 4 ga: 2 → 3 → 4 (6, 5) — 5, to‘g‘ridan-to‘g‘ri yo‘l esa atigi 2. 5-qishloqqa yo‘l yo‘q — -1.