Cow Friendship Graph Modification

Farmer John has N cows numbered from 1 to N (2 ≤ N ≤ 16). The friendship relations among the cows are modeled as an undirected graph with M edges (0 ≤ M ≤ N(N-1)/2). Two cows are friends if and only if there is an edge between them.

In one operation, you can either add an edge or remove an edge from the graph. Your task is to determine the minimum number of operations required so that the following property holds:

For every pair of cows a and b that are friends (i.e. an edge (a,b) exists), for every other cow c (c ≠ a, c ≠ b), at least one of a or b is friends with c. In other words, for every edge (a, b) in the graph, the union of their neighbors must cover all vertices except a and b. Formally, if we denote by \(N(x)\) the set of neighbors of vertex \(x\) in the graph, then for every edge \((a,b)\) we require \[ N(a) \cup N(b) = \{1,2,\dots,N\} \setminus \{a,b\}. \] (Here all formulas are written in \(\LaTeX\) format.)

Observation: One may prove that any graph satisfying the above property must have the following structure: either the graph has no edges at all, or there is a nonempty set \(U\) (of "universal vertices") such that every vertex in \(U\) is adjacent to every other vertex, every vertex outside \(U\) is adjacent to all vertices in \(U\) (and no two vertices outside \(U\) are adjacent). In particular, valid graphs are exactly one of the following:

• An edgeless graph (this occurs when \(U=\emptyset\)).
• A graph with a unique universal vertex (a star graph) or with more than one universal vertex. In these cases, if \(U\) is the set of universal vertices (with \(U \neq \emptyset\)), then for any pair \(i,j\):
  • If at least one of \(i,j\) belongs to \(U\), an edge must be present.
  • If neither \(i\) nor \(j\) belongs to \(U\), no edge is allowed.

Your task is to determine the minimum number of edge modifications (additions or removals) needed to transform the given graph into one that satisfies the property above.

Input Format: The first line contains two integers N and M. Each of the next M lines contains two integers a and b (1 ≤ a, b ≤ N, a ≠ b) indicating that there is an edge between cow a and cow b. There is at most one edge between any pair of cows.

Output Format: Output a single integer representing the minimum number of operations required.

inputFormat

The first line contains two integers N and M. (2 ≤ N ≤ 16, 0 ≤ M ≤ N(N-1)/2)

Each of the next M lines contains two integers a and b, meaning there is an edge between cows a and b.

outputFormat

Output a single integer — the minimum number of operations (edge additions or removals) required to transform the graph so that for every edge (a, b), for every cow c (c ≠ a, b), at least one of a or b is friends with c.

sample

2 0

0