← 返回题目列表

Codeforces · 1090/D

D. 类似数组

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

Vasya 有一个 $$$n$$$ 整数数组,数组的每个元素从 $$$1$$$ 到 $$$n$$$。他选择了$$$m$$$对不同的位置并将它们写在一张纸上。然后瓦夏比较了这些位置的元素,并将比较结果写在另一张纸上。对于每一对,他写下“更大”、“更少”或“等于”。

几年后,他找到了第一张纸,但找不到第二张纸。而且他也不记得自己拥有的阵法。特别是,他不记得数组是否具有相等的元素。他向他的信息学老师海伦博士讲述了这个悲伤的故事。

她告诉他,即使Vasya找到他的第二张纸,他仍然无法找出数组是否有两个相等的元素。

现在 Vasya 想要找到两个整数数组,每个数组的长度为 $$$n$$$。第一个数组的所有元素必须不同,第二个数组中必须有两个相等的元素。对于 Vasya 在第一张纸上写下的每一对位置,第一个数组的相应元素和第二个数组的相应元素的比较结果必须相同。

帮助 Vasya 找到两个这样的长度为 $$$n$$$ 的数组,或者找出他的配对集合中不存在这样的数组。

输入

输入的第一行包含两个整数 $$$n$$$、$$$m$$$——数组中的元素数量和 Vasya 进行的比较次数($$$1 \le n \le 100\,000$$$、$$$0 \le m \le 100\,000$$$)。

以下 $$$m$$$ 行中的每一行都包含两个整数 $$$a_i$$$、$$$b_i$$$ — 第 $$$i$$$ 比较的位置 ($$$1 \le a_i, b_i \le n$$$; $$$a_i \ne b_i$$$)。保证任何无序对在输入中最多给出一次。

输出

输出的第一行必须包含“是"如果存在两个数组,使得比较结果相同,并且第一个数组中的所有数字都不同,而第二个数组包含两个相等的数字。否则它必须包含“NO".

如果数组存在,则第二行必须包含不同整数的数组,第三行必须包含至少包含一对相等元素的数组。数组的元素必须是从 $$$1$$$ 到 $$$n$$$ 的整数。

示例

输入
复制

1 0

输出
复制

NO

输入
复制

3 1
1 2

输出
复制

YES
1 3 2 
1 3 1 

输入
复制

4 3
1 2
1 3
2 4

输出
复制

YES
1 3 4 2 
1 3 4 1