#abc308h. [abc308_h]Make Q
[abc308_h]Make Q
Problem Statement
There is a simple undirected graph with vertices and edges. The edges are initially painted white. The vertices are numbered through , and the edges are numbered through . Edge connects vertex and vertex , and the cost required to paint it black is .
"Making a Q" means painting four or more edges so that:
- all but one of the edges painted black form a simple cycle, and
- the edge painted black not forming the cycle connects a vertex on the cycle and another not on the cycle.
Determine if one can make a Q. If one can, find the minimum total cost required to make a Q.
Constraints
- , if .
- All input values are integers.
Input
The input is given from Standard Input in the following format:
Output
If one can make a Q, print the minimum total cost required to do so; otherwise, print .
Sample Input 1
Sample Output 1
By painting edges , and ,
- edges , and forms a simple cycle, and
- edge connects vertex (on the cycle) and vertex (not on the cycle),
so one can make a Q with a total cost of . Making a Q in another way costs or greater, so the answer is .