You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

在现实世界里，XL 和 CQ 正在玩一个基于二进制数组的《你画我猜》。这个游戏的规则是这样的：

1. XL 将会选取一个长为 $n$ 的数组 $a$，数组由 $0$ 和 $1$ 组成（当然，可以是全 $0$ 和全 $1$），并对 CQ 保密；
2. XL 将会给 CQ 提供 $m$ 条线索，第 $i$ 条线索包含三个整数 $x_i, y_i, z_i$ $(1 \leq x_i < y_i \leq n)$，代表 $a_{x_i}+a_{y_i}+z_i$ 为偶数；
3. CQ 可以向 XL 提问，一次提问可以确定任意一个元素的值；
4. 如果 CQ 可以用最少的提问数量猜出数组，那么 CQ 就获胜了。

CQ 听说你编程能力很好，于是请你帮他求出提问数量的最小值，从而赢下这一局。

输入格式

第一行包含两个整数 $n, m$ $(2 \leq n \leq 10 ^ 5, 1 \leq m \leq 10 ^ 5)$，代表数组 $a$ 的元素个数和线索个数。

接下来包含 $m$ 行，第 $i$ 行包含 $3$ 个整数 $x_i, y_i, z_i$ $(1 \leq x_i < y_i \leq n, 1 \leq z_i \leq 100)$，代表第 $i$ 条线索。

输入保证有解。

输出格式

输出一行一个整数 $x$，代表提问数量的最小值。

3 1
1 2 1

2

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

2

100000 1
1 100000 100

99999

提示

对于样例 $1$，唯一的线索是 $a_1 + a_2 + 1$ 为偶数，你可以提问 $a_1, a_3$，并通过线索推断出 $a_2$，从而需要两次提问。

上述数量最少的提问方式不唯一。