题目描述

有 $N$ 张牌以背面朝上排成一行。!每张牌上都写着一个整数 1 或 2.

设 $A_i$ 是第$i$张牌上写着的整数。

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

你已知以下事实:

·对于每个$i= 1,2,…, M$，$A_{Xi} + A_{Yi} + Z_i$的值是偶数。

你是位魔术师，可以使用以下魔术任意次数:

魔术:选择一张牌并知道上面写着的整数 $A_i$,。使用这个魔术的消费是 1。

确定所有的 $A_1,A_2,…, A_N$ 最少需要多少消费?

输入保证给定输入没有矛盾。

输入

第一行两个整数$N,M$ 接下来一共$M$行，分别表示$X_i,Y_i,Z_i$的值

输出

输出最小总花费，这个消费是确定所有的$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

提示

$2 \leq N \leq 10^5$

$2 \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$满足条件。）