1 或 2

题目描述

$N$ 张卡片一列排开扣放着，每张卡片上写着整数 $1$ 或 $2$。

设第 $i$ 张卡片上写着的整数为 $A_i$。

你的目标是猜出 $A_1, A_2, ..., A_N$。

已知以下事实：

• 对 $i = 1, 2, ..., M$，$A_{X_i} + A_{Y_i} + Z_i$ 是偶数。

你是一名魔法师。可以任意次使用以下魔法。

魔法：支付 $1$ 点代价。选择一张卡片，得知该卡片上写着的整数 $A_i$。

至少需要支付多少代价，才能确保猜出全部的 $A_1, A_2, ..., A_N$ 呢？

题目保证给出的输入没有矛盾。

输入格式

输入按以下格式从标准输入给出：

$N$ $M$
$X_1$ $Y_1$ $Z_1$
$X_2$ $Y_2$ $Z_2$
$\vdots$
$X_M$ $Y_M$ $Z_M$

输出格式

输出为了确保猜出全部的 $A_1, A_2, ..., A_N$ 而需要支付的代价总和的最小值。

样例

3 1
1 2 1

2

对第 $1$ 张和第 $3$ 张卡片各使用 $1$ 次魔法，就可以猜出全部的 $A_1, A_2, A_3$。

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

2

100000 1
1 100000 100

99999

数据范围

• 输入均为整数
• $2 \le N \le 10^5$
• $1 \le M \le 10^5$
• $1 \le X_i \lt Y_i \le N$
• $1 \le Z_i \le 100$
• 所有 $(X_i, Y_i)$ 组合互不相同
• 给出的输入没有矛盾（即存在满足条件的 $A_1, A_2, ..., A_N$）