Эта задача отличается от упрощённой версии. В этой версии задачи Уджана может сделать не более \(2n\) обменов. Кроме того, \(k \le 1000, n \le 50\) и необходимо вывести сами обмены. Вы можете взламывать эту задачу тогда, когда решите ее. Но предыдущую только тогда, когда решите обе задачи.
После долгих страданий и многих неуспешных попыток Уджан решил снова попробовать прибраться в своём доме. Вначале он решил привести в порядок свои строки.
У Уджана есть две различные строки \(s\) и \(t\) длины \(n\), которые содержат только строчные буквы английского алфавита. Он хочет сделать их одинаковыми. Так как Уджан ленивый, он выполнит следующую операцию не более \(2n\) раз: он выбирает два индекса \(i\) и \(j\) (\(1 \le i,j \le n\), значения \(i\) и \(j\) могут как совпадать, так и различаться), и меняет местами буквы \(s_i\) и \(t_j\).
Цель Уджан сделать строки \(s\) и \(t\) равными. Уджану не нужно минимизировать количество операций. Его устроит любой способ, который содержит \(2n\) или менее операций.
Выходные данные
Для каждого набора входных данных выведите «Yes», если Уджан может сделать строки одинаковыми за \(2n\) или менее операций, и «No» в противоположном случае. Вы можете выводить каждую букву в любом регистре (строчную или заглавную).
В случае положительного ответа в следующую строку выведите целое число \(m\) (\(1 \le m \le 2n\)), где \(m\) — количество операций в ответе. Затем выведите \(m\) строк, где каждая строка содержит два целых числа \(i, j\) (\(1 \le i, j \le n\)), которые обозначают что во время соответствующей операции Уджан обменивает символы \(s_i\) и \(t_j\). Вам не нужно минимизировать количество операций. Любой способ сделать это за \(2n\) или менее операций является корректным ответом.