#Algo1006. Lights G

    ID: 192 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>搜索深度优先搜索数学高斯消元luogu2009USACO

Lights G

题目背景

English Edition

题目描述

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

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

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

输入格式

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

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

输出格式

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

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

3 

提示

对于 100%100\% 的数据,1n35,1m595,1a,bn1\le n\le35,1\le m\le595, 1\le a,b\le n