最少选出的同色侧

难度：T4

【知识点：二分图判定】

前置知识：二分图判定及其冻结前置单元。

题目描述与输入

第一行$n$ $m$，随后$m$行$u$ $v$ $w$（$w=1$）表示无向冲突关系。把所有点二染色，每条边两端异色。在每个连通块任选其中一种颜色的全部点，求总选点数最少是多少；允许空侧。

输出

不可二染色输出-$1$，否则输出最少选点数。

数据范围

$1 \le n \le 80$，$0 \le m \le 500$，$w$固定为$1$。无向图允许重边、自环、孤立点。

样例输入

4 4
1 2 1
2 3 1
3 4 1
4 1 1

样例输出

2

样例说明

唯一连通块的两侧都是$2$个点，取任一侧共$2$个。