A2792. Lights G
编程题
提高+/省选-
知识点
题目描述
给出一张 $n$ 个点 $m$ 条边的无向图，每个点的初始状态都为 $0$。
你可以操作任意一个点，操作结束后该点以及所有与该点相邻的点的状态都会改变，由 $0$ 变成 $1$ 或由 $1$ 变成 $0$。
你需要求出最少的操作次数，使得在所有操作完成之后所有 $n$ 个点的状态都是 $1$。
你可以操作任意一个点，操作结束后该点以及所有与该点相邻的点的状态都会改变，由 $0$ 变成 $1$ 或由 $1$ 变成 $0$。
你需要求出最少的操作次数，使得在所有操作完成之后所有 $n$ 个点的状态都是 $1$。
输入格式
第一行两个整数 $n, m$。
之后 $m$ 行，每行两个整数 $a, b$，表示在点 $a, b$ 之间有一条边。
之后 $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$。保证没有重边和自环。