Some travelling salesmen would like to market their fine wares to 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 roads (and that each bidirectional road takes an hour to traverse) how long will it take for the salesmen to visit every city?
Note: You may assume that there are at least salesmen at each company office. Also, all cities will be connected to at least one company office.
Following this will be lines, each describing a road from city to city .
, the number of company offices.
Following this will be lines, each with the location of a company office.
Bonus: one case will have , .
The number of hours it will take for news of the product to spread.
4 3 1 2 2 3 3 4 2 1 2
City 4 will be visited last.