← 返回题目列表

AtCoder · past202109_m

M. 平衡

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

分数: 6 点

警告

2021 年 10 月 2 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违规, 可能会要求赔偿。考试结束后,您可以向以下人员透露您的总分和等级 其他,但仅此而已(例如,您解决了哪些问题)。

问题陈述

给你一个简单的连通无向图 G 与 N 顶点和 M 边缘。
顶点已编号 1, \ldots, N,并且边缘已编号 1, \ldots, M。边缘 i 连接顶点 A_i 和 B_i.

边缘 i 有一个整数 C_i 。你要写一个整数而不是 小于 0 在每个顶点上,以满足以下条件。

条件:对于每条边 i,顶点上写入的数字之和 A_i 和 B_i 等于 C_i.

如果可能,请展示一种方法;如果不可能,请报告这一事实。

约束

  • 2 \leq N \leq 10^5
  • N-1 \leq M \leq 10^5
  • 1 \leq A_i < B_i \leq N
  • 对 (A_i, B_i) 是不同的。
  • 0 \leq C_i \leq 10^9
  • 给定的图形已连接。
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N M
A_1 B_1 C_1
\vdots
A_M B_M C_M

输出

如果没有办法写数字来满足条件,则打印 -1.
否则,打印要在 Vertex 上写入的数字 i 在 i第行,对于 总计 N 行。


示例输入 1

3 2
1 2 2
2 3 1

示例输出 1

1
1
0

可以验证,写 顶点上的 1 在顶点上 1, 1 在顶点上 2,和 0 在顶点上 3 满足条件。

满足条件的另一种方法是写 2 在顶点上 1, 0 上 顶点 2,和 1 在顶点上 3.


示例输入 2

3 3
1 2 0
2 3 0
1 3 2

示例输出 2

-1

注意,写在顶点上的数字必须是不小于的整数 0.