왕국의 분할

바이트란드의 왕 Byteasar가 마침내 은퇴하기로 했다. 그에게는 아들이 둘 있는데, 누구에게 왕위를 물려줄지 정하지 못했다. 그래서 그는 왕국을 두 개의 절반으로 나누어 각 아들에게 하나씩 다스리게 하려 한다.

분할이 끝나면 두 절반을 잇는 모든 도로 옆에 감시탑을 세워야 한다. 감시탑을 세우는 데에는 비용이 많이 들기 때문에, 두 절반 사이를 잇는 도로가 되도록 적어지게 나누어야 한다.

바이트란드에는 짝수 개의 도시가 있고, 도시들은 도로로 연결되어 있다. 분할 후 각 절반은 정확히 전체 도시의 절반씩을 가져야 한다. 각 도로는 두 도시를 직접 잇는다. 도로는 도시에서만 만나며(고가도로나 터널로 지나갈 수도 있다), 어떤 두 도시 사이에도 도로는 많아야 하나만 있다.

도시 바깥의 땅은 언제나 적절히 배치할 수 있어서, 같은 절반에 속한 두 도시를 잇는 도로는 경계선을 넘지 않는다고 가정해도 된다. 감시탑은 서로 다른 절반에 속한 두 도시를 잇는 도로에만 필요하다.

도시와 도로의 정보를 읽어, 왕국을 크기가 같은 두 절반으로 나누는 모든 방법을 고려하여, 필요한 감시탑의 최소 개수, 즉 서로 다른 절반에 속한 도시들을 잇는 도로 수의 최솟값을 구하라.

첫째 줄에 두 정수 $n$과 $m$이 공백 하나로 구분되어 주어진다. 각각 도시의 수와 도로의 수를 나타내며, $2 \le n \le 26$, $n$은 짝수, $0 \le m \le \frac{n(n-1)}{2}$이다. 도시는 $1$번부터 $n$번까지 번호가 매겨져 있다.

이어지는 $m$개의 줄에는 각각 두 정수 $u_i$와 $v_i$가 주어지며($1 \le u_i < v_i \le n$), 도시 $u_i$와 $v_i$를 잇는 도로를 나타낸다.

정수 하나를 출력한다. 세워야 하는 감시탑의 최소 개수이다. 즉, 왕국을 각각 정확히 $\frac{n}{2}$개의 도시를 갖는 두 절반으로 나누는 모든 방법 중에서, 양 끝 도시가 서로 다른 절반에 속하는 도로 수의 최솟값을 출력한다.

그림의 점선은 최적의 분할을 보여준다. 도시를 크기가 같은 두 절반으로 나누면서 감시탑을 가장 적게 세우는 방법이다.