QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100

# 4892. 序列

Statistics

题目描述

有一个长度为 $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, \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}$