Problem E: PIPI的灯泡Ⅱ

Problem E: PIPI的灯泡Ⅱ

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 76  Solved: 17
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI把n个灯泡用m个电线连接了起来(n个灯泡不一定完全连通),每个灯泡都有一个按钮控制,每次按下灯泡状态就会进行改变(从熄灭到点亮或者相反)。不过它设置的电路有点奇怪——当PIPI按下某个灯泡的按钮时,连同这个灯及其由一根电线直接相连的灯的状态都会改变。初始时灯泡都是灭的,PIPI想知道最少操作多少次可以使所有灯泡都点亮?

Input

单组输入。
第一行两个整数n,m,分别表示灯泡的数量和电线的数量。n<=35,m<=595,
接下来m行,每行两个整数u,v,表示每根电线连接的两个灯泡编号。灯泡编号从1开始。

Output

输出一个整数,表示最少操作多少次。如果无解,输出-1.

Sample Input

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

Sample Output

3