Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии вам нужно вывести корректную последовательность операций, если она существует. Вы можете делать взломы только в том случае, если решили все версии этой задачи.
У Кевина есть неориентированный граф с \(n\) вершинами и \(m\) рёбрами. Изначально некоторые вершины содержат камни, которые Кевин хочет переместить на новые позиции.
Кевин может выполнять следующую операцию:
- Для каждого камня на \(u_i\) выбрать соседнюю вершину \(v_i\). Одновременно переместить каждый камень из \(u_i\) на соответствующую ему \(v_i\).
В любой момент каждая вершина может содержать не более одного камня.
Определите, существует ли корректная последовательность операций, которая перемещает камни из начального состояния в целевое. Выведите корректную последовательность операций, содержащую не более \(2n\) операций, если она существует. Можно доказать, что если существует корректная последовательность, то существует и корректная последовательность, содержащая не более \(2n\) операций.
Выходные данные
Для каждого набора входных данных на отдельной строке выведите «Yes» или «No» — существует ли допустимая последовательность операций.
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.
Если существует корректная последовательность операций, во второй строке выведите единственное целое число \(k\) (\(0 \leq k \leq 2n\)), обозначающее количество операций. Предположим, что в исходном состоянии имеется \(c\) камней. Каждая из следующих \(k + 1\) строк должна содержать \(c\) различных целых чисел, представляющих положение камней до операций и после каждой операции. Эти позиции должны удовлетворять следующим требованиям:
- Расположение камней в первой строке соответствует исходному состоянию из входных данных в любом порядке.
- Расположение камней в последней строке соответствует целевому состоянию из входных данных в любом порядке.
- Для всех \(i\) (\(1\leq i\leq k\)) и \(j\) (\(1\leq j\leq c\)) убедитесь, что \(j\)-е целое число в \(i\)-й строке и \(j\)-е целое число в \((i+1)\)-й строке соответствуют соседним вершинам в графе. Другими словами, камень перемещается из своего предыдущего положения в следующее.
Если существует несколько решений, выведите любое из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2 1
10
01
1 2
11 11
11011001010
01101011100
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 1
3 2
110
101
1 2
2 3
3 2
111
111
1 2
2 3
|
Yes
1
1
2
Yes
6
1 2 4 5 8 10
2 3 5 6 9 11
3 2 6 7 10 1
4 3 7 8 11 2
5 2 8 9 1 3
6 3 7 8 2 4
7 2 8 9 3 5
No
Yes
0
1 2 3
|