AT_abc126_e [ABC126E] 1 or 2

题目描述

有 $N$ 张卡片按顺序面朝下排列，每张卡片上写有整数 $1$ 或 $2$。

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

你的目标是猜出 $A_1, A_2, \ldots, A_N$ 的值。

你已知以下信息：

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

你是一名魔法师，可以无限次使用以下魔法。

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

你最少需要支付多少代价，才能确保猜出所有 $A_1, A_2, \ldots, A_N$ 的值？

保证输入数据没有矛盾（即一定存在满足条件的 $A_1, A_2, \ldots, 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, \ldots, A_N$ 所需支付的最小总代价。

样例 1

输入

3 1
1 2 1

输出

2

样例 2

输入

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

输出

2

样例 3

输入

100000 1
1 100000 100

输出

99999

说明/提示

限制条件

• 所有输入均为整数。
• $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$
• $(X_i, Y_i)$ 的组合互不相同。
• 输入保证无矛盾（即存在满足条件的 $A_1, A_2, \ldots, A_N$）。

样例解释 1

对第 $1$ 张和第 $3$ 张卡片各使用一次魔法，就可以确定 $A_1, A_2, A_3$ 的所有值。

由 ChatGPT 4.1 翻译