E - 1 或者 2

得分：500 分

题目描述

有 $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$

$\vdots$

$X_M$ $Y_M$ $Z_M$

输出

输出最小总消费，这个消费是确定所有的 $A_1, A_2, ..., A_N$ 所需要的。

3 1
1 2 1

2

对于第一张牌和第三张牌，使用魔术可以确定 $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