H2. Кевин и камни (сложная версия)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии вам нужно вывести корректную последовательность операций, если она существует. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

У Кевина есть неориентированный граф с $$$n$$$ вершинами и $$$m$$$ рёбрами. Изначально некоторые вершины содержат камни, которые Кевин хочет переместить на новые позиции.

Кевин может выполнять следующую операцию:

  • Для каждого камня на $$$u_i$$$ выбрать соседнюю вершину $$$v_i$$$. Одновременно переместить каждый камень из $$$u_i$$$ на соответствующую ему $$$v_i$$$.

В любой момент каждая вершина может содержать не более одного камня.

Определите, существует ли корректная последовательность операций, которая перемещает камни из начального состояния в целевое. Выведите корректную последовательность операций, содержащую не более $$$2n$$$ операций, если она существует. Можно доказать, что если существует корректная последовательность, то существует и корректная последовательность, содержащая не более $$$2n$$$ операций.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1\leq n \leq 2000$$$, $$$0\leq m \leq \min(\frac{n(n-1)}{2}, 10^4)$$$) — количество вершин и рёбер в графе.

Вторая строка содержит бинарную строку $$$s$$$, состоящую из '0' и '1'. $$$i$$$-й символ $$$s$$$ обозначает количество камней в $$$i$$$-й вершине в исходном состоянии.

Третья строка содержит бинарную строку $$$t$$$, состоящую из '0' и '1'. $$$i$$$-й символ $$$t$$$ обозначает количество камней в $$$i$$$-й вершине в целевом состоянии.

Каждая из следующих $$$m$$$ строк содержит два целых числа $$$u$$$ и $$$v$$$ ($$$1\leq u, v \leq n$$$) — существует неориентированное ребро между вершинами $$$u$$$ и $$$v$$$.

Гарантируется, что граф прост, то есть в графе нет петель и кратных рёбер.

Гарантируется, что количество '1' в $$$s$$$ и $$$t$$$ совпадает.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2000$$$.

Гарантируется, что сумма значений $$$m$$$ по всем наборам входных данных не превосходит $$$10^4$$$.

Выходные данные

Для каждого набора входных данных на отдельной строке выведите «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)$$$-й строке соответствуют соседним вершинам в графе. Другими словами, камень перемещается из своего предыдущего положения в следующее.

Если существует несколько решений, выведите любое из них.

Пример
Входные данные
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