안전한 건설 계획

숭실대학교는 새로운 고층 건물을 설계하고 있다.

지금까지 쌓아 올린 건물의 골조는 수직으로 세운 $N$개의 기둥과, 서로 다른 두 기둥을 수평으로 잇는 $M$개의 빔으로 이루어져 있다. 평면도에서 기둥은 점으로, 빔은 두 점을 잇는 선분으로 나타낸다. 기둥은 1번부터 $N$번까지, 빔은 1번부터 $M$번까지 번호가 붙어 있다.

건물의 안정성을 높이려고 보강 작업을 여러 차례 진행한다. 목표는 서로 다른 모든 두 기둥을 빔으로 잇는 것이며, 빔은 모두 합해 $N(N-1)/2$개가 된다. 기둥이 5개라면 평면도는 아래 그림과 같아야 한다.

구조물의 하중을 버티려면 보강 작업을 삼각형을 쌓는 방식으로 해야 한다. 작업 한 번에는 서로 다른 세 기둥 $a, b, c$를 골라 $(a,b)$, $(b,c)$, $(c,a)$ 세 쌍을 모두 빔으로 잇고, 삼각형을 한 번에 만든다. 이때 세 기둥 사이에 이미 있던 빔의 개수에 따라 비용이 달라진다.

• 세 기둥 사이에 빔이 하나도 없으면 위험도가 높아서 진행할 수 없다.
• 빔이 1개 있으면 빔 2개가 추가되어 삼각형이 만들어진다. 주의가 필요한 작업이므로 비용은 1이다.
• 빔이 2개 있으면 빔 1개가 추가되어 삼각형이 만들어진다. 비교적 안전하므로 비용은 0이다.
• 빔이 3개 모두 있으면 이미 삼각형이 구성되어 있으므로 아무것도 하지 않는다.

보강 작업을 0회 이상 원하는 만큼 진행해서 모든 기둥 사이에 빔이 존재하도록 할 때, 최소 비용을 구하라. 모든 입력에 대해 서로 다른 두 기둥을 잇는 빔이 항상 존재하도록 보강 작업을 진행할 수 있음이 보장된다.

예를 들어 골조의 평면도가 위 그림과 같고, 왼쪽 위의 점부터 시계 방향으로 1, 2, 3, 4번 기둥이라고 하자.

첫 번째 보강 작업에서 1, 2, 3번 기둥으로 삼각형을 만들고, 두 번째 보강 작업에서 1, 2, 4번 기둥으로 삼각형을 만들면 총비용은 1+1=2이다.

반면 첫 번째 보강 작업에서 1, 2, 3번 기둥, 두 번째에서 2, 3, 4번 기둥, 세 번째에서 1, 2, 4번 기둥을 고르면 총비용은 1+0+0=1이다.

이 밖에도 여러 방법이 있지만 비용을 1보다 적게 쓰는 방법은 없으므로 답은 1이다.

첫째 줄에 기둥의 개수 $N$과 빔의 개수 $M$이 공백으로 구분되어 주어진다.

둘째 줄부터 $M+1$번째 줄까지, $i+1$번째 줄에 $i$번째 빔이 연결하는 두 기둥의 번호 $a_i$, $b_i$가 공백으로 구분되어 주어진다.

보강 작업을 최적으로 진행할 때, 서로 다른 모든 기둥을 빔으로 잇도록 만드는 최소 비용을 출력한다.

• $3 \le N \le 40$
• $1 \le M \le N(N-1)/2$
• $1 \le a_i < b_i \le N$ ($1 \le i \le M$)
• $i \ne j$이면 $(a_i,b_i) \ne (a_j,b_j)$이다. ($1 \le i,j \le M$) 즉, 같은 두 기둥을 잇는 빔이 여러 개 존재하지 않는다.
• 서로 다른 두 기둥을 잇는 빔이 항상 존재하도록 보강 작업을 진행할 수 있음이 보장된다.
• 입력으로 주어지는 수는 모두 정수이다.