2013年7月9日 星期二

11377 - Airport Setup


Problem A
Airport Setup
Time Limit: 3 Second


在"無名" 王國中,有 N 個城市,其中 K 個城市設有機場。航空公司將要規劃 M 條直接抵達的航班,他們認為其他直飛路線是不符合利益的。當兩座城市都有機場時,並且起點與終點是在 M 條中被規劃的,飛機才會對飛班次。由於並不是每個城市都有機場以及航空公司開的班次,因此人們無法不一定能靠飛機來做為交通工具抵達目的地。
所以城市中的人們向國王請求,他們希望能藉由飛機飛往目的地(包括轉機)。接下來國王收到 Q 筆詢問,每筆詢問 (x, y) 表示想要路線從城市 x 飛往城市 y,國王真心想要滿足這些詢問,但他不想建造太多的機場,因此他想要建造最少的機場數從 x 到 y。

Input:
第一行,有一個整樹 X (≦ 10) 表示測資筆數,每組測資包含三個整數 N ( 1 ≤ N ≤ 2,000), M ( 0 ≤ M ≤ 10,000), K ( 1 ≤ K ≤ N),N 代表有城市數量,M 表示直飛的航班規劃數量,K 表示已經建造的機場數量,接下來會有 K 個整數表示具有機場的節點編號,接下來會有 M 行,每行上會有兩個整數 a, b,表示航班可以對飛 a, b。
下一行會有一個整數 Q ( 1 ≤ Q ≤ 50 ),表示詢問的數量,接下來會有 Q 行 x, y 表示起點 x 到終點 y。

Output:
對於每組輸出測資組數,然後對於詢問輸出最少建造的機場數量,如果沒辦法滿足需求,則輸出 "-1",對於每組測資之後都輸出一行換行。


SAMPLE INPUT
OUTPUT FOR SAMPLE INPUT
1
6 4 4
1 2 5 6
1 2
3 5
2 4
4 5
3
1 2
1 3
1 6

Case 1:
0
2
-1



Problemsetter: Tasnim Imran Sunny
Special Thanks To: Md. Mahbubul Hasan

沒有留言:

張貼留言