[AdditionalFile3629.zip](file://AdditionalFile3629.zip?type=additional_file)

#3629. 「2021 集训队互测」序列

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

有一个长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$，序列里的每个元素都是 $[1,10^9]$ 内的正整数。

现在已知了 $m$ 条信息，每条信息形如 $i,j,k,x$，表示这个序列满足 $a_i+a_j+a_k−\max(a_i,a_j,a_k)−\min(a_i,a_j,a_k)=x$。

请构造一个满足条件的序列。

输入格式

第一行两个正整数 $n,m$。

接下来 $m$ 行，每行四个正整数 $i,j,k,x$，表示一条信息。

输出格式

如果无解，第一行输出 NO。

如果有解，第一行输出 YES。第二行输出 $n$ 个正整数 $a_1,a_2,…,a_n$，表示你构造的满足条件的序列 $a$，你需要保证每个 $a_i$ 都是 $[1,10^9]$ 内的正整数。

样例 1

输入

6 4
1 3 4 2
1 2 5 6
3 6 6 7
2 4 5 3

输出

YES
6 8 2 2 3 7

样例 2

输入

5 4
1 2 3 4
2 3 4 5
3 4 5 3
1 3 4 6

输出

NO

数据范围与提示

对于全部数据，$1≤n,m≤10^5,1≤i,j,k≤n,1≤x≤10^9$。

• 子任务 $1$（$20$ 分）：$n,m≤10$。
• 子任务 $2$（$10$ 分）：$m=\binom n 3$，且对于任意一条信息，$i≠j,j≠k,k≠i$，对于任意一个满足条件的集合 $\{i,j,k\}$，在信息中恰好出现一条。
• 子任务 $3$（$30$ 分）：$n,m≤1000$。
• 子任务 $4$（$40$ 分）：无特殊限制。