分数: 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