OI题库

【问题描述】

元宵节快要到了，某城市人民公园将举办一次灯展。Dr.Kong准备设计出一个奇妙的展品，他计划将编号为1到N的N（1 <= N <= 35）盏灯放置在一个有M条（1 <= M <= 595）边连接的网络节点上。

   每盏灯上面都带有一個开关。当按下某一盏灯的开关時，这盏灯本身以及与之有边相连的灯的状态就会改变。状态改变指的是：当一盏灯是亮时，就会被关闭；当一盏灯是关闭时，就会被打开亮着。

现在的问题是，你能帮助Dr.Kong计算一下最少要按下多少个开关，才能把所有的灯都打开亮着（初始状态：所有的灯都是关闭的）。

数据保证至少有一种按开关的方案，使得所有的灯都能被重新打开。

输入格式：

第1行:   N  M

第2到第M+1行：每一行有两个由空格隔开的整數，表示两盏灯被一条边连接。

输出格式：

 一个整数，表示要把所有的灯都打开时，最少需要按下的开关次数。

输入样例

5 6

1 2

1 3

4 2

3 4

2 5

5 3

输出样例  

3