(flow.*)

Trước tình trạng giao thông tại địa bàn phường Thống Nhất của môt thành phố A, với mật độ phương tiện tham gia giao thông rất đông nên hay xảy ra ùn tắc cục bộ ở một số tuyến đường, đặc biệt là giờ cao điểm thường bị kẹt xe, gây ảnh thưởng đến các hoạt động giao thương và các hoạt động khác của phường. Trước tình hình trên, giám đốc công an thành phố A đã cử anh Hoàng là công an giao thông thành phố A về phường Thống Nhất làm công tác điều tra mức độ kẹt xe nhiều nhất trên từng nút giao thông trong phường, để trình lên công an thành phố tìm phương án giải quyết tình trạng kẹt xe ở trên.

Có thể coi hệ thống giao thông của phường Thống Nhất gồm \(n\) nút giao thông khác nhau với \(m\) đoạn đường nối giữa chúng. Do hệ thống đường của phường được làm tự phát, không theo quy hoạch nên từ một nút giao thông này luôn có thể đến một nút giao thông khác và những đoạn đường đi không tạo ra chu trình (từ một nút giao thông đi qua các nút giao thông khác, mỗi nút giao thông đi không quá một lần thì không có đường đi trở lại chính nó). Đoạn đường \(u,\ v\) nối hai nút giao thông \(u,\ v\) có độ rộng là \(w\). Vì hàng ngày luôn có nhiều phương tiện giao thông qua lại giữa những nút giao thông trong phường, nên anh Hoàng muốn biết từ một nút giao thông \(a\) bất kỳ tới một nút giao thông \(b\) bất kỳ, độ kẹt đường lớn nhất của đoạn đường đó là bao nhiêu. Bạn hãy giúp anh Hoàng trả lời \(q\) câu hỏi này.

Độ kẹt đường lớn nhất của một con đường từ nút giao thông \(a\) tới nút giao thông \(b\) được định nghĩa như sau: Ta có thể chọn bất kì con đường từ \(a\) tới \(b\) sao cho mỗi đoạn đường trên con đường đó có độ rộng dương. Sau đó với mỗi đoạn đường trên con đường đó, trừ độ rộng đi 1 đơn vị và cộng 1 vào kết quả. Lặp đi lặp lại với số lần ta thích. Độ kẹt đường lớn nhất của hai nút giao thông là kết quả lớn nhất tìm được, nếu chọn con đường tối ưu nhất.

Ví dụ: Độ kẹt đường lớn nhất từ nút giao thông \(s\) tới nút giao thông \(t\) trong một khu vực nào đó như sau:

Độ kẹt đường lớn nhất trong khu vực này là 3

Cách chọn tối ưu là

s – A – C – t và s – B – D – E - t

Nếu chọn con đường s – A – C – t và s – B – C – t thì độ kẹt đường là 2, không phải độ kẹt đường lớn nhất

Dữ liệu vào:

+ Dòng thứ nhất chứa hai số nguyên dương \(n,\ m\);

+ \(m\) dòng tiếp theo, mỗi dòng chứa 3 số nguyên \(u,\ v,\ w\ (1 \leq w \leq 10^{9},u
eq v)\) cho biết đoạn đường từ nút giao thông \(u\) tới nút giao thông \(v\) có độ rộng \(w\);

+ Dòng tiếp theo chứa số nguyên dương \(q\);

+ \(q\) dòng tiếp theo, mỗi dòng chứa 2 số nguyên \(a,\ b\ (1 \leq a,b \leq n,\ a
eq b)\) là tham số của từng truy vấn;

Kết quả:

+ Ghi \(q\) dòng số nguyên là kết quả của \(q\) truy vấn.

Ràng buộc:

+ Có 30% số test ứng với 30% số điểm của bài thoả mãn điều kiện \(n,\ q\ \leq \ 10^{3}\);

+ 70% số test còn lại ứng với 70% số điểm của bài thỏa mãn điều kiện \(n,\ q \leq 10^{5}\).

Ví dụ: