Chain Repair#11060
Sovunya had a chain consisting of links, numbered from to . But while the chain was lying in the dresser, it got all tangled up. Sovunya wants to fix the situation.
Each link is a ring of wire. Each pair of links is either connected to each other or not. Sovunya turned to Pin for help. He can perform two actions:
Unlink one of the links. Thus, it ceases to be a closed ring, and therefore it can be detached from all the other links.
Re-solder a previously unlinked link. Thus, it becomes a closed ring again. Pin can choose an arbitrary set of other links, thread the current link through them before soldering, and thus connect this link to each of the selected set.
In the end, all links must be soldered.
Sovunya wants link number to be connected to link number , to , ..., n - 1 to . In other words, links numbered and i + 1 should be connected for all i \in [1, n - 1]. And no other pairs of links should be connected.
Help Pin determine the minimum number of actions he has to perform to fix the chain.
The first line contains two integers and m~(1 \le n \le 40, 0 \le m \le n \cdot (n - 1) / 2) — the number of links and the number of initially connected pairs of links.
In the next lines, there are two integers a_i and b_i~(1 \le a_i, b_i \le n, a_i \ne b_i) — the numbers of connected links.
It is guaranteed that each unordered pair of links appears at most once in the input data.
Output one integer — the minimum number of actions Pin must perform to fix the chain.
In the first example, Pin can unlink link number . Then it will detach from both remaining links. And then, re-solder link number , connecting it only with link number .
In the second example, Pin can unlink link number , then re-solder it back connecting it with links and . And then, unlink link number and re-solder it back, connecting it with links and .
Example 1
Example 2
Example 3