1163 . 6.施工中的道路
TopCoder
Tags
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 1
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 1
-1
Hints
Problem Source
原TIOJ1163 / 96 TWN Practice Contest 4。Problem Setter：???。
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 33 |
| 2 | 1 | 33 |
| 3 | 2 | 34 |