#P1770. [Usaco2009 Nov]lights 燈

    ID: 792 传统题 1000ms 256MiB 尝试: 1186 已通过: 399 难度: 5 上传者: 标签>CF1800普及+/提高-异或抵消状态编码折半枚举全子集枚举两半结果排序匹配二分查找消除被支配候选Gold

[Usaco2009 Nov]lights 燈

题目描述

给出一张 nn 个点 mm 条边的无向图,每个点的初始状态都为 00。

你可以操作任意一个点,操作结束后该点以及所有与该点相邻的点的状态都会改变,由 00 变成 11 或由 11 变成 00。

你需要求出最少的操作次数,使得在所有操作完成之后所有 nn 个点的状态都是 11。

输入格式

第一行两个整数 n,mn, m。

之后 mm 行,每行两个整数 a,ba, b,表示在点 a,ba, b 之间有一条边。

输出格式

一行一个整数,表示最少需要的操作次数。

本题保证有解。

样例 #1

样例输入 #1

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

样例输出 #1

3

提示

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