C - Bipartize Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB



配点 : 350 点

問題文

N 頂点 M 辺の単純な無向グラフがあります。 グラフは頂点 1, 頂点 2,\ldots, 頂点 N からなり、i 番目 (1\le i\le M) の辺は頂点 u _ i と頂点 v _ i を結んでいます。

あなたは、次の操作を 0 回以上行います。

  • まだ削除されていない辺をひとつ選び、削除する。

あなたの目的はグラフを二部グラフにすることです。 操作を行ったあとのグラフを二部グラフにするために、最低でも何回操作を行う必要があるか求めてください。

グラフが単純であるとは

グラフが単純であるとは、自己ループ（u _ i=v _ i となる辺）や多重辺（u _ i=u _ j かつ v _ i=v _ j となる辺のペア）が存在しないことをいいます。

二部グラフとは

二部グラフとは、頂点をそれぞれ黒か白のどちらか一色で塗り、次の条件を満たすことができるグラフのことをいいます。

  • どの辺についても、その辺が結んでいるふたつの頂点に塗られた色は異なる。

制約

  • 2\le N\le10
  • 1\le M\le\dfrac{N(N-1)}2
  • 1\le u _ i\lt v _ i\le N\ (1\le i\le M)
  • 与えられるグラフは単純
  • 入力はすべて整数

入力

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

N M
u _ 1 v _ 1
u _ 2 v _ 2
\vdots
u _ M v _ M

出力

操作を行ったあとのグラフを二部グラフにするために、行う必要がある操作の回数を出力せよ。

入力例 1

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

出力例 1

2

例えば、頂点 1 と頂点 3 を結ぶ辺、頂点 3 と頂点 5 を結ぶ辺の 2 つを削除することでグラフを二部グラフにすることができます。

操作を 1 回以下行うことでグラフを二部グラフにすることはできないため、2 を出力してください。

入力例 2

2 1
1 2

出力例 2

0

グラフははじめから二部グラフです。 よって、行う必要がある操作の回数は 0 回です。

入力例 3

10 20
5 9
1 4
3 8
1 6
4 10
5 7
5 6
3 7
3 6
5 10
1 3
3 4
6 7
1 2
4 7
1 5
1 9
9 10
4 5
8 9

出力例 3

5

Score : 350 points

Problem Statement

There is a simple undirected graph with N vertices and M edges. The graph consists of vertex 1, vertex 2,\ldots, vertex N, and the i-th edge (1\le i\le M) connects vertices u _ i and v _ i.

You will perform the following operation zero or more times:

  • Choose one edge that has not been deleted yet, and delete it.

Your goal is to make the graph bipartite. Find the minimum number of operations needed to make the graph after the operations bipartite.

What it means for a graph to be simple?

A graph is simple if and only if it has no self-loops (edges where u _ i=v _ i) or multi-edges (pairs of edges where u _ i=u _ j and v _ i=v _ j).

What is a bipartite graph?

A bipartite graph is a graph where it is possible to color each vertex black or white satisfying the following condition:

  • For every edge, the two vertices connected by that edge have different colors.

Constraints

  • 2\le N\le10
  • 1\le M\le\dfrac{N(N-1)}2
  • 1\le u _ i\lt v _ i\le N\ (1\le i\le M)
  • The given graph is simple.
  • All input values are integers.

Input

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

N M
u _ 1 v _ 1
u _ 2 v _ 2
\vdots
u _ M v _ M

Output

Print the number of operations that need to be performed to make the graph bipartite.

Sample Input 1

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

Sample Output 1

2

You can make the graph bipartite by deleting two edges: for example, the edge connecting vertices 1 and 3, and the edge connecting vertices 3 and 5.

It is impossible to make the graph bipartite by performing one or less operations, so print 2.

Sample Input 2

2 1
1 2

Sample Output 2

0

The graph is bipartite from the beginning. Thus, the number of operations that need to be performed is 0.

Sample Input 3

10 20
5 9
1 4
3 8
1 6
4 10
5 7
5 6
3 7
3 6
5 10
1 3
3 4
6 7
1 2
4 7
1 5
1 9
9 10
4 5
8 9

Sample Output 3

5