E - 1 or 2 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

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 全てを確実に当てることができるでしょうか。

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

制約

  • 入力は全て整数である。
  • 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 が存在する)。

入力

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

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

3 1
1 2 1

出力例 1

2

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

入力例 2

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

出力例 2

2

入力例 3

100000 1
1 100000 100

出力例 3

99999

Score : 500 points

Problem Statement

There are N cards placed face down in a row. On each card, an integer 1 or 2 is written.

Let A_i be the integer written on the i-th card.

Your objective is to guess A_1, A_2, ..., A_N correctly.

You know the following facts:

  • For each i = 1, 2, ..., M, the value A_{X_i} + A_{Y_i} + Z_i is an even number.

You are a magician and can use the following magic any number of times:

Magic: Choose one card and know the integer A_i written on it. The cost of using this magic is 1.

What is the minimum cost required to determine all of A_1, A_2, ..., A_N?

It is guaranteed that there is no contradiction in given input.

Constraints

  • All values in input are integers.
  • 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
  • The pairs (X_i, Y_i) are distinct.
  • There is no contradiction in input. (That is, there exist integers A_1, A_2, ..., A_N that satisfy the conditions.)

Input

Input is given from Standard Input in the following format:

N M
X_1 Y_1 Z_1
X_2 Y_2 Z_2
\vdots
X_M Y_M Z_M

Output

Print the minimum total cost required to determine all of A_1, A_2, ..., A_N.

Sample Input 1

3 1
1 2 1

Sample Output 1

2

You can determine all of A_1, A_2, A_3 by using the magic for the first and third cards.

Sample Input 2

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

Sample Output 2

2

Sample Input 3

100000 1
1 100000 100

Sample Output 3

99999