Safe Construction Plan

Sungsil University is designing a new high-rise building.

The frame built so far consists of $N$ columns standing vertically and $M$ beams that connect two different columns horizontally. In the floor plan, columns are drawn as points and beams as segments connecting two points. Columns are numbered 1 to $N$, and beams are numbered 1 to $M$.

To strengthen the building, the university will carry out several reinforcement jobs. The goal is to install beams so that every pair of different columns is connected, which means $N(N-1)/2$ beams in total. For 5 columns, the floor plan should look like the figure below.

To carry the load of the structure, reinforcement must be done by stacking triangles. One job picks three different columns $a, b, c$ and adds the beams for all three pairs $(a,b)$, $(b,c)$, $(c,a)$ at once, forming a triangle. The cost depends on how many beams already exist among the three columns.

• If no beam exists among the three columns, the risk is high, so the job cannot be done.
• If one beam exists, two beams are added to form the triangle. This job needs care, so it costs 1.
• If two beams exist, one beam is added to form the triangle. This job is relatively safe, so it costs 0.
• If all three beams exist, the triangle is already formed, so nothing is done.

Perform the reinforcement jobs zero or more times, as many as you want, so that beams exist between every pair of columns. Find the minimum total cost. For every input, it is guaranteed that the reinforcement jobs can be carried out so that a beam connects every pair of different columns.

For example, suppose the floor plan is as in the figure above, and the columns are numbered 1, 2, 3, 4 clockwise starting from the top-left point.

In the first job, make a triangle with columns 1, 2, 3. In the second job, make a triangle with columns 1, 2, 4. The total cost is 1+1=2.

On the other hand, choose columns 1, 2, 3 in the first job, 2, 3, 4 in the second, and 1, 2, 4 in the third. The total cost is 1+0+0=1.

There are many other ways, but no method uses less than 1 unit of cost, so the answer is 1.

The first line contains the number of columns $N$ and the number of beams $M$, separated by a space.

From the second line through line $M+1$, line $i+1$ contains the two column numbers $a_i$ and $b_i$ connected by the $i$-th beam, separated by a space.

When the reinforcement jobs are carried out optimally, print the minimum cost needed so that a beam connects every pair of different columns.

• $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$)
• For $i \ne j$, $(a_i,b_i) \ne (a_j,b_j)$. ($1 \le i,j \le M$) In other words, no two beams connect the same pair of columns.
• It is guaranteed that the reinforcement jobs can be carried out so that a beam connects every pair of different columns.
• All input numbers are integers.