Subdivision of Kingdom

Byteasar, king of Byteotia, has finally decided to retire. He has two sons but cannot decide which of them should succeed him, so he plans to split the kingdom into two halves and make each son a ruler.

After the division, a watchtower must be built beside every road that connects the two halves. Watchtowers are expensive, so the split should cross as few roads as possible.

Byteotia consists of an even number of towns connected by roads. After the division each half must contain exactly half of the towns. Each road directly connects two towns; roads meet only at towns (they may run through flyovers or tunnels), and every pair of towns is joined by at most one road.

You may assume the land outside the towns can always be arranged so that a road between two towns in the same half never crosses the border. A watchtower is needed only for a road that joins two towns lying in different halves.

Read the towns and the roads, consider every way to divide the kingdom into two halves of equal size, and report the smallest possible number of watchtowers, that is, the minimum number of roads that connect towns lying in different halves.

The first line contains two integers $n$ and $m$ separated by a single space: the number of towns and the number of roads, where $2 \le n \le 26$, $n$ is even, and $0 \le m \le \frac{n(n-1)}{2}$. The towns are numbered from $1$ to $n$.

Each of the next $m$ lines contains two integers $u_i$ and $v_i$ with $1 \le u_i < v_i \le n$, describing a road that connects towns $u_i$ and $v_i$.

Print a single integer: the minimum number of watchtowers that must be built. Equivalently, over all divisions of the kingdom into two halves that each contain exactly $\frac{n}{2}$ towns, print the smallest possible number of roads whose two endpoints lie in different halves.

The dashed line in the figure shows an optimum division: it splits the towns into two equal halves while requiring the fewest watchtowers.