[USACO09NOV] Lights G

题目背景

[English Edition](/paste/410oq6t5)

题目描述

给出一张 $n$ 个点 $m$ 条边的无向图,每个点的初始状态都为 $0$。 你可以操作任意一个点,操作结束后该点以及所有与该点相邻的点的状态都会改变,由 $0$ 变成 $1$ 或由 $1$ 变成 $0$。 你需要求出最少的操作次数,使得在所有操作完成之后所有 $n$ 个点的状态都是 $1$。

输入输出格式

输入格式


第一行两个整数 $n, m$。 之后 $m$ 行,每行两个整数 $a, b$,表示在点 $a, b$ 之间有一条边。

输出格式


一行一个整数,表示最少需要的操作次数。 本题保证有解。

输入输出样例

输入样例 #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$。保证没有重边和自环。