Задачи
Weird Coloring
Weird Coloring
You are given an undirected graph \textbf{G}. You should paint the edges of \textbf{G} with colors \textbf{0}, \textbf{1}, \textbf{2}, ... such that:
\begin{enumerate}
\item Sum of colors of all edges be minimum.
\item For each edge with color \textbf{0}, there must be an adjacent edge such that the color of that edge is \textbf{2}. Two edges are adjacent if they have a common vertex.
\end{enumerate}
\InputFile
First line of Input contains the number of the tests.
For each case, first you are given \textbf{1} ≤ \textbf{n} ≤ \textbf{20} and \textbf{1} ≤ \textbf{m} ≤ \textbf{30}, the number of vertices and edges respectively. In the following \textbf{m} lines, in each line you are given two endpoints of an edge.
\OutputFile
For each case, output minimum number of sum of the edges that have appropriate properties.
Входные данные #1
2 3 3 1 2 2 3 1 3 18 27 1 2 1 4 1 6 3 2 3 4 3 6 2 5 4 5 7 8 7 10 7 12 9 8 9 10 9 12 8 11 10 11 13 14 13 16 13 18 15 14 15 16 15 18 14 17 16 17 5 11 12 17 18 6
Выходные данные #1
2 14