[ABC126E] 1 or 2

题面翻译

有一个含有 $N(2\le N\le 10^5)$ 个数的序列 $A$。序列中数仅含有 $1$ 和 $2$。

你不知道这个序列的具体内容，但是你知道 $M(1\le M\le 10^5)$ 组关系。每组关系形如 $X_i\ \ Y_i\ \ Z_i$，表示 $A_{X_i}+A_{Y_i}+Z_i$ 为偶数。

问：当你知道了这些关系之后，你最少需要确定多少个序列中的数才能进而确定整个序列。

题目描述

$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$ 払う。カードを $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$ 全てを確実に当てるために払う必要のあるコストの合計の最小値を出力せよ。

样例 #1

样例输入 #1

3 1
1 2 1

样例输出 #1

2

样例 #2

样例输入 #2

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

样例输出 #2

2

样例 #3

样例输入 #3

100000 1
1 100000 100

样例输出 #3

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,\ ...,\ A_N$ が存在する)。

Sample Explanation 1

$1$ 枚目と $3$ 枚目のカードに対してそれぞれ $1$ 回ずつ魔法を使えば、$A_1,\ A_2,\ A_3$ 全てを当てることができます。