← 返回题目列表

Codeforces · 1187/C

C. Vasya 和阵列

中文机器翻译题面 查看原题

Vasya 有一个数组 $$$a_1, a_2, \dots, a_n$$$。

你不知道这个数组,但他告诉了你关于这个数组的$$$m$$$事实。第 $$$i$$$ 事实是数字 $$$t_i$$$、$$$l_i$$$ 和 $$$r_i$$$ 的三元组 ($$$0 \le t_i \le 1, 1 \le l_i < r_i \le n$$$),这意味着:

- 如果 $$$t_i=1$$$ 则子数组 $$$a_{l_i}, a_{l_i + 1}, \dots, a_{r_i}$$$ 按非降序排序;
- 如果 $$$t_i=0$$$ 则子数组 $$$a_{l_i}, a_{l_i + 1}, \dots, a_{r_i}$$$ 不按非降序排序。如果子数组中至少有一对连续元素且前者大于后者,则该子数组不会被排序。

例如,如果 $$$a = [2, 1, 1, 3, 2]$$$ 那么他可以给你三个事实: $$$t_1=1, l_1=2, r_1=4$$$ (子数组 $$$[a_2, a_3, a_4] = [1, 1, 3]$$$ 已排序), $$$t_2=0, l_2=4、r_2=5$$$(子数组 $$$[a_4, a_5] = [3, 2]$$$ 未排序),$$$t_3=0、l_3=3, r_3=5$$$(子数组 $$$[a_3, a_5] = [1, 3, 2]$$$ 未排序)。

你不知道数组$$$a$$$。找到满足所有给定事实的任何数组。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 1000, 1 \le m \le 1000$$$)。

接下来的 $$$m$$$ 行包含三个整数 $$$t_i$$$、$$$l_i$$$ 和 $$$r_i$$$ ($$$0 \le t_i \le 1, 1 \le l_i < r_i \le n$$$)。

如果 $$$t_i = 1$$$ 则对子数组 $$$a_{l_i}, a_{l_i + 1}, \dots , a_{r_i}$$$ 进行排序。否则(如果 $$$t_i = 0$$$)子数组 $$$a_{l_i}, a_{l_i + 1}, \dots , a_{r_i}$$$ 不会排序。

输出

如果没有数组仅在行中满足这些事实,则打印 NO(任何字母大小写)。

如果有解决方案,请打印 YES(任何字母大小写)。在第二行中打印 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 数组 $$$a$$$,满足所有给定的事实。如果有多个令人满意的数组,您可以打印其中任何一个。

示例

输入 #1

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

输出 #1

YES
1 2 2 3 5 4 4

输入 #2

4 2
1 1 4
0 2 3

输出 #2

NO