Travelling Salesmen

Some travelling salesmen would like to market their fine wares to several cities in a faraway country.
Salesmen can be found at company offices, which can be found in a select few of these cities.
Now, given that the cities are connected with many roads (and that each bidirectional road takes an hour to traverse) how long will it take for the salesmen to visit every city?

Input

N ≤ 1,000, M ≤ 100,000.
Following this will be M lines, each describing a road from city a to city b.
K ≤ N, the number of company offices.
Following this will be K lines, each with the location of a company office.
Bonus: one case will have N, K ≤ 30,000.

Output

The number of hours it will take for news of the product to spread.

Sample Input

4 3
1 2
2 3
3 4
2
1
2

Sample Output

2

City #4 will be visited last.

All Submissions
Best Solutions

Point Value: 10
Time Limit: 2.00s
Memory Limit: 32M
Added: Mar 04, 2009

Problem Types: [Show] [Hide]

• Graph Theory

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)