题目描述

有 $N$ 张卡片背面朝上排成一行。每张卡片上写着整数 1 或 2。

设 $A_i$ 表示第 $i$ 张卡片上写的整数。

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

你知道以下事实：

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

作为一名魔术师，你可以使用以下魔法任意次数：

魔法：选择一张卡片并得知上面写的整数 $A_i$。使用这个魔法的代价是 1。

确定所有的 $A_1, A_2, ..., A_N$ 最小代价是多少？

保证输入中没有矛盾。

约束条件

• 输入中的所有值均为整数。
• $2 \leq N \leq 10^5$
• $1 \leq M \leq 10^5$
• $1 \leq X_i < Y_i \leq N$
• $1 \leq Z_i \leq 100$
• 对于所有的 $i$，$(X_i, Y_i)$ 是不同的。
• 输入中没有矛盾。（也就是说，存在满足条件的整数 $A_1, A_2, ..., A_N$）

输入

从标准输入读取输入数据，输入格式如下：

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

输出

输出确定所有的 $A_1, A_2, ..., A_N$ 的最小总代价。

示例输入 1

3 1
1 2 1

示例输出 1

2

你可以用魔法猜测第一张卡片和第三张卡片上的整数来确定 $A_1, A_2, A_3$。

示例输入 2

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

示例输出 2

2

示例输入 3

100000 1
1 100000 100

示例输出 3

99999