Description

Bessie and the cows were playing games in the barn, but the power was reset and the lights were all turned off. Help the cows get all the lights back on so they can resume their games.

The N (1 <= N <= 35) lights conveniently numbered 1..N and their switches are arranged in a complex network with M (1 <= M <= 595) clever connection between pairs of lights (see below).

Each light has a switch that, when toggled, causes that light -- and all of the lights that are connected to it -- to change their states (from on to off, or off to on).

Find the minimum number of switches that need to be toggled in order to turn all the lights back on.

It's guaranteed that there is at least one way to toggle the switches so all lights are back on.

Input format

• Line 1: Two space-separated integers: N and M.
• Lines 2..M+1: Each line contains two space-separated integers representing two lights that are connected. No pair will be repeated.

Output format

• Line 1: A single integer representing the minimum number of switches that need to be flipped in order to turn on all the lights.

Explanation

There are 5 lights. Lights 1, 4, and 5 are each connected to both lights 2 and 3.

Toggle the switches on lights 1, 4, and 5.

翻译题面：

[USACO09NOV] Lights G

题目背景

描述

贝西和奶牛们在谷仓里玩游戏，但电源被重置了，所有的灯都熄灭了。帮助奶牛们把所有的灯都打开，这样它们就可以继续玩游戏了。

N（1 <= N <= 35）盏灯方便地编号为1..N，它们的开关被安排在一个复杂的网络中，有M（1 <= M <= 595）个巧妙的连接对。

每个开关控制一盏灯，当切换时，会导致那盏灯——以及所有与它相连的灯——改变状态（从开变为关，或从关变为开）。

找出需要切换的最少开关数量，以便把所有的灯都打开。

保证至少有一种方式切换开关，使所有的灯都重新亮起。

输入格式

• 第1行：两个用空格分隔的整数：N和M。
• 第2行到M+1行：每行包含两个用空格分隔的整数，代表两个相连的灯。

输出格式

• 第1行：一个整数，代表需要翻转的最少开关数量，以便打开所有的灯。

解释

有5盏灯。灯1、4和5分别连接到灯2和3。

切换灯1、4和5上的开关。

样例 #1

样例输入 #1

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

样例输出 #1

3

提示

对于 $100\%$ 的数据，$1\le n\le35,1\le m\le595, 1\le a,b\le n$。保证没有重边和自环。