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$ 所需支付的最小总代价。

## 限制条件 - 所有输入均为整数。 - $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 翻译