CF1090D Similar Arrays

Vasya 有一个长度为 $n$ 的整数数组，数组中的每个元素都是 $1$ 到 $n$ 之间的整数。他选择了 $m$ 对不同的位置，并把这些位置对写在了一张纸上。然后 Vasya 比较了这些位置上的元素，并把比较的结果写在了另一张纸上。对于每一对位置，他会写下“更大”、“更小”或“相等”。 多年以后，他找到了第一张纸，但找不到第二张纸了。他也不记得原来的数组是什么，甚至不记得数组中是否有相等的元素。他把这个悲伤的故事告诉了他的计算机老师 Dr Helen。 老师告诉他，即使找到了第二张纸，他也可能无法确定数组中是否有两个相等的元素。 现在 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$）。保证任意无序对在输入中最多只出现一次。

输出的第一行为 "YES"，如果存在满足条件的两个数组；否则输出 "NO"。 如果存在这样的数组，第二行输出第一个数组（所有元素互不相同），第三行输出第二个数组（至少有一对元素相等）。数组中的元素必须是 $1$ 到 $n$ 之间的整数。

由 ChatGPT 4.1 翻译