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