TopCoder

WeaK
weak.infor.org 雖然這裡好像沒什麼東西。

User's AC Ratio

85.7% (18/21)

Submission's AC Ratio

37.7% (29/77)

Description

有一天,時弦無意間聽到了黑暗騎士憂鬱人士的對話:

「最近家裡附近的道路又在整修了,我等了三天才有通路連到這裡,真是科科。」
「哭哭啦,你比我好多了。從我家到這裡的路蓋了五天才蓋好咧。」

時弦聽了以後覺得很有趣,於是就把他們兩人的對話對照了地圖:

地圖上每個點都是一個地方,而每一條邊上面所寫的數字代表第幾天以後該道路才會通。
例如要有一條從A走到D的道路需要等到第三天才能通行。

「如果我隨便指定兩個點,要如何很快地知道這兩個地點要等到第幾天才有連接的道路呢?」

時弦想了很久,決定請TDY好威幫忙。哪知道TDY好威一下子就解決了這個問題,卻不告訴時弦
他說:「你應該自己想出來的,這個題目根本就是秒殺嘛…」
四處求助無門的時弦,決定把解決這個問題的重責大任交給你!

Input Format

輸入檔只包含一筆測試資料。

第一列有兩個正整數V,E,分別代表地圖上的頂點個數以及邊的個數。
地圖上頂點的編號是從1編號到V。

第2~E+1列每一列有三個正整數 X,Y,d(1<=X,Y<=V, 1<=d<231),分別代表該無向邊所連接的兩個頂點,d代表此道路開通的時間。

第E+2列只有一個正整數Q,代表詢問的個數。

然後的Q列每一列有兩個正整數 ST,ED(1<=ST,ED<=V)代表每個詢問內容:起點與終點。

由於時弦是個好學而且踏實的人,再加上大頭蕃真的是超級心機,他們所給你的地圖絕對不會是簡單的地圖。
這個圖上面的點最多可能有30,000個,圖上的邊最多可能有50,000條。而詢問的總數也不會超過50,000個。

Output Format

對於每個詢問請你輸出一個數字,代表兩地存在連通道路的最早時間。若兩地至老死不相往來,請輸出-1。若詢問的兩個地點相同,請輸出0。

Sample Input

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

Sample Output

3
-1

Hints

Problem Source

原TIOJ1163 / 96 TWN Practice Contest 4。Problem Setter:???。

Subtasks

For Testdata: 0 ~ 0, Score: 33
For Testdata: 1 ~ 1, Score: 33
For Testdata: 2 ~ 2, Score: 34
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536