G - Make 2-Regular Graph Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 425 点

問題文

N 頂点 M 辺の単純無向グラフ G があります。頂点には 1, 2, \ldots, N の番号が付けられており、i 番目の辺は頂点 A_i と頂点 B_i を結ぶ無向辺です。

あなたは、以下の 2 つの操作を好きな順序で好きな回数繰り返すことができます。

  • G に無向辺を 1 つ追加する
  • G から無向辺を 1 つ削除する

G をすべての頂点の次数が 2 である単純無向グラフにするために行う操作回数として考えられる最小値を求めてください。

単純無向グラフとは

単純無向グラフとは、自己ループと多重辺を持たない無向グラフのことを指します。

制約

  • 3 \leq N \leq 8
  • 0 \leq M \leq \frac{N(N-1)}{2}
  • 入力で与えられるグラフ G は単純無向グラフ
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N M
A_1 B_1 
\vdots
A_M B_M

出力

答えを出力せよ。

入力例 1

5 4
1 2
1 5
2 4
4 5

出力例 1

3

例えば以下のようにすることで、3 回の操作で G をすべての頂点の次数が 2 の単純無向グラフにすることができます。

  • 頂点 2 と頂点 3 を結ぶ辺を追加する。
  • 頂点 2 と頂点 4 を結ぶ辺を削除する。
  • 頂点 3 と頂点 4 を結ぶ辺を追加する。

入力例 2

3 0

出力例 2

3

入力例 3

6 8
1 4
1 5
2 3
2 6
3 4
3 6
4 5
4 6

出力例 3

2

入力例 4

8 21
1 4
5 7
8 4
3 4
2 5
8 1
5 1
2 8
2 1
2 4
3 1
6 7
5 8
2 7
6 8
5 4
3 8
7 3
7 8
5 3
7 4

出力例 4

13

Score : 425 points

Problem Statement

There is a simple undirected graph G with N vertices and M edges. The vertices are numbered 1, 2, \ldots, N, and the i-th edge is an undirected edge connecting vertices A_i and B_i.

You can repeat the following two operations in any order and any number of times:

  • Add one undirected edge to G
  • Remove one undirected edge from G

Find the minimum number of operations to make G a simple undirected graph where all vertices have degree 2.

What is a simple undirected graph?

A simple undirected graph refers to an undirected graph that has no self-loops and no multi-edges.

Constraints

  • 3 \leq N \leq 8
  • 0 \leq M \leq \frac{N(N-1)}{2}
  • The graph G given in the input is a simple undirected graph.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
A_1 B_1 
\vdots
A_M B_M

Output

Output the answer.

Sample Input 1

5 4
1 2
1 5
2 4
4 5

Sample Output 1

3

For example, the following three operations make G a simple undirected graph where all vertices have degree 2.

  • Add an edge connecting vertices 2 and 3.
  • Remove the edge connecting vertices 2 and 4.
  • Add an edge connecting vertices 3 and 4.

Sample Input 2

3 0

Sample Output 2

3

Sample Input 3

6 8
1 4
1 5
2 3
2 6
3 4
3 6
4 5
4 6

Sample Output 3

2

Sample Input 4

8 21
1 4
5 7
8 4
3 4
2 5
8 1
5 1
2 8
2 1
2 4
3 1
6 7
5 8
2 7
6 8
5 4
3 8
7 3
7 8
5 3
7 4

Sample Output 4

13