Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

KNIGHTS1 - Knights

Một đất nước nọ có N châu. Các châu được đánh số từ 1 đến N. Các châu được nối với nhau bằng các con đường có độ dài là một số nguyên dương nào đó.

Các kị binh này thường xuyên bị điều động đi tuần giữa các châu bằng ngựa. Khi đi giữa các châu, các kị binh không quan tâm độ dài của cả tuyến đường đi mình tuần mà chỉ quan tâm đến độ dài con đường ngắn nhất mà họ phải đi qua. Họ muốn đi sao cho con đường dài nhất mà họ đi qua trên tuyến đường đó càng dài thì con ngựa cưỡi càng có nguy cơ bị mệt mà chết.

Cho các thông tin về các tuyến đường giữa các châu, hãy giúp các chàng kị binh xác định độ dài tuyến đường dài nhất mà họ phải đi qua nếu muốn đi giữa hai châu nào đó.

Input

Dòng đầu ghi hai số nguyên dương N và R. N là số châu, R là số tuyến đường hai chiều giữa các châu. (1<=N<=3000, 1<=r<=100000). Mỗi dòng trong R dòng tiếp theo ghi ba số a,b và l: thể hiện có một con đường nối từ châu a đến châu b với độ dài l (1<=a,b<=N, 1<=l<=1000000). Dòng tiếp theo ghi số nguyên dương Q (1<=Q<=1000) là số câu mà các kị binh cần bạn trả lời. Mỗi dòng trong Q dòng tiếp theo ghi hai số a và b thể hiện câu hỏi: Nếu đi từ k đến t thì độ dài đường đi dài nhất trên tuyến đường đi nào đó nối từ k đến t ngắn nhất có thể là bao nhiêu (1<=k,t<=N, k<>t).

Output

Tương ứng với mỗi câu hỏi ghi một dòng trả lời, dòng này chứa đúng một số là độ dài đường đi dài nhất trên tuyến đường đi nào đó nối từ a đến b ngắn nhất có thể là bao nhiêu.

Sample Input

6 9

2 4 5

5 1 7

3 6 6

3 1 4

2 3 2

1 2 1

6 5 42

4 5 3

4 6 5

4

1 3

3 4

5 4

6 1

Sample Output

2

5

3

5


Được gửi lên bởi:Trần Hải Đăng
Ngày:2010-11-20
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED

hide comments
2010-12-06 14:27:01 Dra Tiny
Luồng?? :-?
2010-11-23 21:02:36 dhkhtn
Q<=1000 thoi, cai quan trong vay ma PS quen mat T.T
2010-11-23 14:17:04 Siêu Nhân Trong Suốt
MÌNH QUÁ XUI ĐI :(

Last edit: 2010-11-23 23:23:26
2010-11-23 12:13:06 Voyage
Đề nghị PS bổ sung nguồn gốc bài này: ACM Southwestern European 2008
2010-11-22 05:14:59 Xin_tha_cho_ban_Vuong
À ra thế! Cảm ơn anh.
2010-11-22 04:46:04 Nguyễn Quang Anh
Nó chỉ quan tâm đến ĐOẠN ĐƯỜNG DÀI NHẤT trên con đường nó đi thôi em ạ :D.
2010-11-22 04:43:23 Xin_tha_cho_ban_Vuong
nhưng 6=>4=>2=>1 là 11 rồi mà anh
trong khi 6=>3=>2=>1 có 9 thôi mà
2010-11-22 04:44:32 Nguyễn Quang Anh
6=>4=>2=>1 ma` =.=
2010-11-22 02:23:48 Xin_tha_cho_ban_Vuong
TEST đề bài phải ra là
2 5 3 6
chứ nhỉ.
đường đi ngắn nhất từ 6=>1 là 6=>3=>2=>1 kq là 6 chứ
2010-11-21 16:24:16 ACM ICPC
Q<=?????
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.