#2459. [ABC126E] 1 or 2

[ABC126E] 1 or 2

[ABC126E] 1 or 2

题面翻译

有一个含有 N(2N105)N(2\le N\le 10^5) 个数的序列 AA。序列中数仅含有 1122

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

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

题目描述

N N 枚のカードが一列に伏せられており、各カードには整数 1 1 または 2 2 が書かれています。

i i 番目のカードに書かれている整数を Ai A_i とします。

あなたの目的は A1, A2, ..., AN A_1,\ A_2,\ ...,\ A_N を当てることです。

次のことが分かっています。

  • i = 1, 2, ..., M i\ =\ 1,\ 2,\ ...,\ M について AXi + AYi + Zi A_{X_i}\ +\ A_{Y_i}\ +\ Z_i は偶数である。

あなたは魔法使いです。次の魔法を何度でも使うことができます。

魔法: コストを 1 1 払う。カードを 1 1 枚選び、そのカードに書かれた整数 Ai A_i を知る。

最小で何コスト払えば、A1, A2, ..., AN A_1,\ A_2,\ ...,\ A_N 全てを確実に当てることができるでしょうか。

なお、与えられる入力には矛盾がないことが保証されます。

输入格式

入力は以下の形式で標準入力から与えられる。

N N M M X1 X_1 Y1 Y_1 Z1 Z_1 X2 X_2 Y2 Y_2 Z2 Z_2 \vdots XM X_M YM Y_M ZM Z_M

输出格式

A1, A2, ..., AN 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  N  105 2\ \leq\ N\ \leq\ 10^5
  • 1  M  105 1\ \leq\ M\ \leq\ 10^5
  • 1  Xi < Yi  N 1\ \leq\ X_i\ <\ Y_i\ \leq\ N
  • 1  Zi  100 1\ \leq\ Z_i\ \leq\ 100
  • (Xi, Yi) (X_i,\ Y_i) の組は互いに異なる。
  • 与えられる入力には矛盾がない(すなわち、条件を満たす A1, A2, ..., AN A_1,\ A_2,\ ...,\ A_N が存在する)。

Sample Explanation 1

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