Задача №114480. Похожие массивы
У Васи был массив из \(n\) натуральных чисел от \(1\) до \(n\). Он выбрал \(m\) различных пар различных позиций и записал их на листочек. Затем Вася для каждой пары позиций сравнил между собой находящиеся на них элементы и записал на другой листочек результаты сравнений — «больше», «меньше» или «равно».
Через несколько лет он нашёл свой первый листочек, а второй найти не смог. Кроме того, он совершенно забыл, какой у него был исходный массив. В частности, Вася забыл, были ли в его массиве равные элементы. Он рассказал эту трагическую историю своей учительнице информатики Елене Андреевне.
В ответ она сказала, что может так случиться, что даже если Вася найдет свой второй листочек, информации, записанной на нём, может оказаться недостаточно, чтобы определить, были ли в массиве два равных элемента.
Вася тут же захотел найти два массива натуральных чисел длины \(n\), все элементы первого массива должны быть различны, а во втором массиве должно быть хотя бы два равных элемента. При этом для каждой пары индексов, записанных на первом листочке, результаты сравнений в обоих массивах будут одинаковы.
Помогите Васе найти два массива длины \(n\), удовлетворяющие данным условиям, или выясните, что для его множества пар индексов таких массивов не существует.
В первой строке задано два целых числа \(n\), \(m\) — количество чисел в массиве и количество сравнений, сделанных Васей (\(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\).
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