← 返回题目列表

AtCoder · abc126_e

E. 1 或 2

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

有 N 卡片面朝下排成一排。每张卡上都有一个整数 写入 1 or 2 。

让 A_i 是写在 i第一张卡。

你的目标是猜测 A_1, A_2, ..., A_N 正确。

您知道以下事实:

  • 对于每个 i = 1, 2, ..., M,值 A_{X_i} + A_{Y_i} + Z_i 是偶数。

你是一名魔术师,可以多次使用以下魔法:

魔法: 选择一张牌并知道整数 上面写着 A_i 。使用这个魔法的成本是 1.

确定所有这些所需的最低成本是多少 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

您可以确定所有 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