题目描述
有一个长度为 n 的序列 a1,a2,…,an,序列里的每个元素都是 [1,109] 内的正整数。
现在已知了 m 条信息,每条信息形如 i,j,k,x,表示这个序列满足 ai+aj+ak−max。
请构造一个满足条件的序列。
输入格式
第一行两个正整数 n, m。
接下来 m 行,每行四个正整数 i, j, k, x,表示一条信息。
输出格式
如果无解,第一行输出 NO
。
如果有解,第一行输出 YES
。第二行输出 n 个正整数 a_1, a_2, \dots, 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\leq n,m\leq 10^5,1\leq i,j,k\leq n,1\leq x\leq 10^9。
- 子任务 1(20 分):n,m\leq 10。
- 子任务 2(10 分):m=\binom{n}{3},且对于任意一条信息,i\neq j, j\neq k, k\neq i,对于任意一个满足条件的集合 \{i,j,k\},在信息中恰好出现一条。
- 子任务 3(30 分):n,m\leq 1000。
- 子任务 4(40 分):无特殊限制。
时间限制:1\texttt{s}
空间限制:512\texttt{MB}