Woburn Challenge 2018-19 Round 3 - Senior Division
It's every Pokémon trainer's dream to visit all of the Pokémon gyms in their region, defeating each of their gym leaders and claiming gym badges proving their worth! The members of Team Rocket also dream of visiting all of the gyms, though that's mostly because they're sure to be filled with powerful Pokémon worth stealing…
A certain region has
towns, numbered from
to
. There are
routes running amongst the towns, each of
which allows travelers to walk in either direction between a pair of
towns, such that each town may be reached from any other town by
following a sequence of one or more routes. The
-th route runs
between towns
and
.
There are
Pokémon gyms in the region, the
-th of
which is located in town
. No two gyms are
in the same town, and none of the gyms are in town
.
Team Rocket would like to pay a friendly visit to each gym's town at
least once. They currently find themselves in town , and it takes them
one whole day to walk along a route from their current town to another
town. It takes them no time to conduct any business in the gyms, but all
of this walking looks to be very time-consuming by itself!
Fortunately, another potential method of travel is also available to
them. A winged Pokémon named Dragonite can be found in town
, and Team Rocket may be able to enlist its transportation
services. If they're ever in town
, they may choose to catch
Dragonite. Anytime after they've caught Dragonite, they may choose to
Fly back to any town they've previously visited. Catching Dragonite and
Flying to a previous town each take no time at all. It's guaranteed that
Dragonite is not at a town which has a Pokémon gym.
What's the minimum number of days required for Team Rocket to visit all
gyms after beginning in town
?
Subtasks
In test cases worth of the points,
.
Input Specification
The first line of input consists of three space-separated integers, ,
, and
.
The next line consists of integers, .
lines follow, the
-th of which consists of two integers,
and
, for
.
Output Specification
Output a single integer, the minimum number of days required for Team
Rocket to visit all gyms.
Sample Input 1
4 3 1
3 4 2
1 2
3 2
4 2
Sample Output 1
3
Sample Input 2
5 2 4
2 5
1 2
2 3
3 4
1 5
Sample Output 2
3
Sample Input 3
7 3 2
7 6 3
5 6
4 7
2 4
1 4
6 1
4 3
Sample Output 3
5
Sample Explanation
In the first case, Team Rocket can immediately catch Dragonite in town
. They can then walk to town
followed by town
, visiting both of
their gyms. They can then Fly back to town
, and finally walk from
there to town
to visit its gym. In total, they will have walked from
town to town
times, resulting in the whole tour taking
days.
In the second case, Team Rocket can begin by walking to town and
visiting its gym. They can then walk back to town
and then to town
,
visiting its gym as well.
Comments