老人星上居住著許多的老人，這些老人的年齡高到將近百萬歲都有可能，但也有可能有不幸英年早逝的老人。
某天，老人星上的某個國度軅劁國，被一名名叫鋥盦蘄、可信度很高的巫師預言，軅劁國將會在百萬年內接連受到R顆隕石的襲擊，每一顆隕石都會不偏不倚地打在其中R條負責連接軅劁國的N座城市的E條道路上面，根據時間的不同，每條道路的炸毀時間也會不同，鋥盦蘄勸告軅劁國的M個老人們必須盡速離開軅劁國，免得遭遇不幸。
但軅劁國是一個人民都很固執的國家，沒有一個合理的理由說服這個國家的老人離開，他們是不會輕易離開軅劁國的。
為了解決這個問題，鋥盦蘄分別調查了每個老人的居住習性：如果第i個老人發現了自己的城市所在地可連通到的城市(含自己這座)少於ci座，他便會心生厭惡離開這個城市！
現在你幫鋥盦蘄寫一個程式，給你軅劁國N座城市的連通關係圖，和M個老人的ci，以及R顆隕石掉落下的倒數時間tj年和炸毀的道路編號pj，請幫每個老人找出，使得這位老人可以在定居最久(必須一直符合連通城市≥ci座)的前提下，他必須要在幾年內搬出軅劁國。
輸入首行有四個正整數N,E,R,M以空格隔開。
接著E行，第1+k行有兩個正整數ak,bk以空格隔開，代表城市ak,bk之間有一條連通道路編號為k。
接下來R行各有兩個非負整數tj,pj以空格隔開。
最後一行有M個正整數ci以空格隔開。
請輸出M行，第i行的正整數xi表示第i個老人必須要在xi年內搬出軅劁國。如果這名老人根本本來就不應該住在軅劁國，請改輸出單一一個-1；如果隕石砸完後老人居住的城市還是滿足連通性，請輸出INF。
//輸入範例1 5 6 4 3 1 2 5 1 4 5 2 3 1 3 3 4 1 2 2 6 3 1 4 4 5 3 1 //輸入範例2 5 4 3 3 1 2 3 4 4 5 3 5 6 1 9 2 87 3 5 3 2
//輸出範例1 2 4 INF //輸出範例2 -1 87 INF
本題共有四個子題，每一子題可有多筆測試資料：
第一子題的測試資料 N≤500，M≤103，E≤5×103，全部解出可獲18分；
第二子題的測試資料 N≤105，M=1，E≤5×105，全部解出可獲35分；
第三子題的測試資料 N≤105，M≤105，E≤5×105，全部解出可獲37分；
第四子題的測試資料 N≤105，M≤106，E≤5×105，時限下修至0.5s，全部解出可獲10分。
所有測試資料，1≤a,b,ci≤N，tj≤106，0≤R≤E，1≤pj≤E，ak≠bk。
如果x≠y，則px≠py。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||