Teemo is a small, cute, cat-like creature who likes to plant mushrooms.
The mushrooms will explode to hurt the people who step on it.
Usually Teemo plant many mushrooms to defence his country from being attacked by ugly guys.
Today, Teemo is again ordered to plant mushrooms in every bushes to defence his country.
However, the ugly guys seem so angry (about the mushrooms) today and are all eager to slay Teemo in his mushrooms planting journey.
Teemo does not want to die.
He asks you to calculate the shortest time he needs to plant mushrooms into all bushes.
There is no room for Teemo to give up since his allies will also kill him if he does so.
The map of Teemo's country can be expressed as an undirected graph.
Every vertex is a bush, and there are routes between some bushes.
Teemo always needs 1 second to pass through a route and 3 seconds to plant a mushroom.
Teemo can start or end his journey at any bush.
There are several cases in the input file.
The first line of the input file contains an integer T<=10 specifying the number of cases.
Every case begins with N<=16, the number of bushes, and M<=min(3N,N(N-1)/2), the number of routes.
The following M lines contain two numbers 0<=Ai,Bi<=N-1 each, denoting a route between bush Ai and bush Bi.
For each case, output a number denoting the minimum time needed by Teemo to finish his job.
2 3 3 0 1 1 2 2 0 4 3 0 1 0 2 0 3
11 16
Migrated from old NTUJ.
pP
| No. | Testdata Range | Score |
|---|