곡예사

한 곡예사가 마지막 공연으로 아무도 시도하지 않은 외줄타기를 준비한다. 로프는 이웃한 두 언덕 사이의 깊은 협곡 위에 걸리고, 양쪽 끝은 언덕에 고정하지 않는다. 훈련받은 조수가 손으로 직접 잡는다.

첫 번째 언덕에는 조수 $A_1, A_2, \dots, A_N$이 이 순서로 서 있고, 두 번째 언덕에는 $B_1, B_2, \dots, B_N$이 서 있다. $B_i$는 협곡을 사이에 두고 $A_i$와 마주 본다. 로프 하나는 양쪽 언덕에서 조수 한 명씩, 예를 들어 $A_i$와 $B_j$가 잡는다. 로프가 워낙 팽팽해서 곡예사가 건너는 순간 끊어지므로 같은 로프를 두 번 건널 수 없다.

공연은 이렇게 진행된다. 곡예사는 첫 번째 언덕에 있는 어느 로프 끝에서 출발해 모든 로프를 정확히 한 번씩 건너고 출발한 자리로 돌아온다. 로프 끝에 도착하면 그 자리에 서 있는 조수가 잡고 있는 다른 로프로 이어서 건넌다.

조수들은 곡예사에게 묻지 않고 이미 원하는 대로 로프를 잡았기 때문에 지금 배치로는 공연이 불가능할 수도 있다. 곡예사는 두 종류의 변경을 할 수 있다.

1번 변경: $A_i$와 $B_j$가 잡고 있는 로프를 골라, 두 조수에게 자기 쪽 끝을 마주 선 조수에게 동시에 던지라고 지시한다. 그러면 그 로프는 $B_i$와 $A_j$가 잡는다. 관객이 첫 번째 언덕을 보고 있으므로 로프 하나는 최대 한 번만 던질 수 있고, 곡예사는 이 변경을 되도록 적게 하고 싶다.

2번 변경: 두 번째 언덕은 관객에게서 멀어 눈에 띄지 않으므로, 곡예사는 $B_i$의 자리와 $B_j$의 자리 사이에 걸어서 오갈 길을 낼 수 있다. 2번 변경에는 제약이 없다. 원하는 만큼 낼 수 있고, 같은 두 조수 사이에 여러 개를 낼 수도 있으며, 공연 중에 각 길을 몇 번이든 지나가도 되고 한 번도 지나가지 않아도 된다.

공연이 가능해지는 1번 변경의 최소 횟수를 구하라.

첫째 줄에 두 정수 $N$과 $M$이 주어진다. $N$은 한 언덕에 서 있는 조수의 수이고, $M$은 로프의 수이다. 다음 $M$개의 줄에는 정수 $i$와 $j$가 공백으로 구분되어 주어지며, $A_i$와 $B_j$가 로프 하나를 잡고 있다는 뜻이다. 처음에는 같은 조수 쌍이 로프를 두 개 잡는 경우가 없어서 $M$개의 쌍은 모두 다르다. 1번 변경을 한 뒤에는 같은 쌍이 로프를 두 개 잡을 수도 있다.

공연이 가능해지도록 하는 1번 변경의 최소 횟수를 한 줄에 출력한다. 변경을 몇 번 하더라도 공연이 불가능하면 $-1$을 출력한다.

$1 \le N \le 16$, $1 \le M \le N^2$, $1 \le i, j \le N$이다. $M$개의 쌍 $(i, j)$는 모두 다르다. $i = j$인 로프는 $A_i$와 $B_i$가 잡는다.

그림은 첫 번째 예제를 나타낸다. 왼쪽은 처음 배치, 가운데는 1번 변경을 한 뒤의 배치, 오른쪽은 두 번째 언덕에 길을 낸 모습이다.

첫 번째 예제에서 로프는 $A_2$와 $B_1$, $A_3$와 $B_1$, $A_3$와 $B_2$, $A_1$과 $B_3$가 잡고 있다. $A_2$와 $B_1$이 잡은 로프에 1번 변경을 하면 그 로프는 $B_2$와 $A_1$이 잡는다. 이제 $B_1$과 $B_3$ 사이에 길을 내고 $A_1$, $B_3$, $B_1$, $A_3$, $B_2$, $A_1$ 순서로 걸으면 모든 로프가 끊어지고 출발한 자리로 돌아오므로 1번 변경 한 번으로 충분하다.

두 번째 예제에서는 어떤 순서로 변경해도 첫 번째 언덕의 어느 조수는 로프 끝을 홀수 개 잡게 되므로 공연이 불가능하다.