## 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]

**Languages Allowed:**

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

## Comments (Search)

LucianIleaon Oct 13, 2019 - 4:53:25 pm UTC The real meaning of the problemSerene17on Aug 02, 2015 - 1:05:34 am UTC Clarificationwgma00on Aug 02, 2015 - 1:24:30 am UTC Re: Clarification