[HAOI2013]开关控制

Grade Open Time Friday, 19 September 2014, 10:07 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:07 am
Allow late Yes Close Time Friday, 26 September 2014, 10:07 am
Input file haoi13t3.in Output file haoi13t3.out

【问题描述】

元宵节快要到了,某城市人民公园将举办一次灯展。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