logo AlgoBeat OnlineJudge
登录 注册

#200258. 工程规划

内存限制:125 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

造一幢大楼是一项艰巨的工程,它是由 个子任务构成的,给它们分别编号 。由于对一些任务的起始条件有着严格的限制,所以每个任务的起始时间 并不是很容易确定的(但这些起始时间都是非负整数,因为它们必须在整个工程开始后启动)。例如:挖掘完成后,紧接着就要打地基;但是混凝土浇筑完成后,却要等待一段时间再去掉模板。

这种要求就可以用 个不等式表示,不等式形如 代表 的起始时间必须满足的条件。每个不等式的右边都是一个常数 ,这些常数可能不相同,但是它们都在区间 内。

你的任务就是写一个程序,给定像上面那样的不等式,找出一种可能的起始时间序列 ,或者判断问题无解。对于有解的情况,要使最早进行的那个任务和整个工程的起始时间相同,也就是说, 中至少有一个为

输入格式

第一行是用空格隔开的两个正整数 ,下面的 行每行有三个用空格隔开的整数 对应着不等式

输出格式

如果有可行的方案,那么输出 行,每行都有一个非负整数且至少有一个为 ,按顺序表示每个任务的起始时间。如果没有可行的方案,就输出信息 NO SOLUTION

样例

样例输入 1

5 8
1 2 0
1 5 -1
2 5 1
3 1 5
4 1 4
4 3 -1
5 3 -1
5 4 -3

样例输出 1

0
2
5
4
1

样例输入 2

5 5
1 2 -3
1 5 -1
2 5 -1
5 1 -5
4 1 4

样例输出 2

NO SOLUTION

数据范围与提示

由@zhouyonglong提供SPJ