题目背景
翻译自 NOISG2019 Prelim B.Lost Array。
本题已启用 Special Judge,满足题目条件的任何答案都将视为正确。
题目描述
给定 M 组形如 min(XAi,XBi)=Ci 的关系式,请构造一个长度为 N 的数组 X,使得数组中的每个数字在 1 到 109 之间,并且该数组满足所有的关系式。
题目保证数组存在。
输入格式
第一行两个整数 N,M。
接下来 M 行,每行三个数字 Ai,Bi,Ci。
输出格式
共一行 N 个整数,代表你构造的数组 X。
提示
【样例 #1 解释】
显然,min(X2,X1)=min(9,7)=7,满足题目条件。
【样例 #3 解释】
原题的题面没有此样例,但测试数据有。
第一个限制为 min(X1,X2)=1,所有的条件实际上和这个限制一样。
【样例 #4 解释】
唯一的限制为 min(X1,X2)=123,其余的数字可以是介于 1 到 109 之间的任何数字。
【数据范围】
Subtask |
分值 |
特殊性质 |
0 |
样例 |
1 |
5 |
N=2,M=1 |
2 |
6 |
M≤3 |
3 |
20 |
N,M≤1000 |
4 |
21 |
Ci≤10,N≤5 |
5 |
48 |
无 |
对于 100% 的数据:
- 1≤N,M≤105
- 1≤Ai,Bi≤N
- Ai=Bi
- 1≤Ci≤109