A22503.Lights G

提高+/省选-

USACO

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

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

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

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

输入格式

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

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

输出格式

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

本题保证有解。

输入输出样例

  • 输入#1

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

    输出#1

    3 
    

说明/提示

对于 100%100\% 的数据,1n35,1m595,1a,bn1\le n\le35,1\le m\le595, 1\le a,b\le n。保证没有重边和自环。

首页