#2016. 序列

序列

序列

题目描述

标题: 序列 - Problem - QOJ.ac

#4892. 序列

Statistics

The problem was used in the following contests:

题目描述

有一个长度为 n 的序列 a1,a2,…,an,序列里的每个元素都是 [1,109] 内的正整数。

现在已知了 m 条信息,每条信息形如 i,j,k,x,表示这个序列满足 ai+aj+ak−max(ai,aj,ak)−min(ai,aj,ak)=x。

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

输入格式

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

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

输出格式

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

如果有解,第一行输出 YES。第二行输出 n 个正整数 a1,a2,…,an,表示你构造的满足条件的序列 a,你需要保证每个 ai 都是 [1,109] 内的正整数。

样例 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≤105,1≤i,j,k≤n,1≤x≤109。

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

时间限制:1s

空间限制:512MB

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 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