Олимпиадный тренинг

Задача . D. Приключения Алисы в картах


Алиса играет в карты с Дамой Червей, Королем Червей и Валетом Червей. В их карточной игре есть \(n\) различных типов карт. В данный момент у Алисы есть карта типа \(1\), и ей нужна карта типа \(n\), чтобы сбежать из Страны Чудес. У остальных игроков есть по одной карте каждого типа.

В этой карточной игре Алиса может обмениваться картами с тремя другими игроками. У каждого игрока есть свои предпочтения среди этих \(n\) типов, которые можно описать перестановками\(^{\text{∗}}\) \(q\), \(k\) и \(j\) для Дамы, Короля и Валета соответственно.

Игрок оценивает карту \(a\) больше, чем карту \(b\), если для их перестановки \(p\), \(p_a > p_b\). Тогда этот игрок готов обменять карту \(b\) с Алисой в обмен на карту \(a\). Предпочтения Алисы просты: она оценивает карту \(a\) больше, чем карту \(b\) если \(a > b\), и она будет обмениваться картами только в соответствии с этими предпочтениями.

Определите, может ли Алиса обменять карту типа \(1\) на карту типа \(n\), учитывая эти предпочтения. Если это возможно, приведите возможный набор обменов для этого.

\(^{\text{∗}}\)Перестановкой длины \(n\) является массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) — перестановка, но \([1,2,2]\) не перестановка (\(2\) встречается в массиве дважды) и \([1,3,4]\) тоже не перестановка (\(n=3\), но в массиве встречается \(4\)).

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

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

Первая строка каждого набора входных данных содержит целое число \(n\) (\(2\le n\le 2\cdot 10^5\)) — количество типов карт.

Следующие три строки содержат предпочтения Дамы, Короля и Валета соответственно. Каждая из этих строк содержит \(n\) целых чисел \(p_1, p_2, \ldots, p_n\) (\(1\le p_i\le n\)) — перестановка, соответствующая предпочтениям игрока.

Сумма значений \(n\) по всем наборам входных данных не превосходит \(2\cdot 10^5\).

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

Для каждого набора входных данных в первой строке выведите одну строку «YES» или «NO» (без кавычек), обозначающую, может ли Алиса обменяться на карту \(n\).

Если первая строка была «YES», то на следующей строке выведите \(k\) — количество обменов, которые сделает Алиса. На следующих \(k\) строках выведите через пробел символ \(c\in \{\texttt{q}, \texttt{k}, \texttt{j}\}\) и целое число \(x\), обозначающее, что Алиса обменивается с игроком \(c\), чтобы получить карту \(x\). Должно быть так, что на \(k\)-й строке \(x = n\). Если существует несколько решений, выведите любое из них.

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ. То же самое касается символа \(c\), обозначающего игрока в обмене (\(\texttt{Q}, \texttt{K}, \texttt{J}\) будут приняты наряду с их строчными вариантами).

Примечание

В первом наборе входных данных Алиса может обменяться с Королем, чтобы получить карту \(2\). Затем она может обменяться с Дамой, чтобы получить карту \(3\).

Во втором наборе входных данных, хотя Алиса может обменяться с Дамой, чтобы получить карту \(3\), с Королем, чтобы получить карту \(2\), а затем с Валетом, чтобы получить карту \(4\), это не является допустимым решением, так как оно не соответствует предпочтениям Алисы. Мы можем показать, что нет способа для Алисы получить карту \(4\).


Примеры
№Входные данныеВыходные данные
1
2
3
1 3 2
2 1 3
1 2 3
4
2 3 1 4
1 2 3 4
1 4 2 3
YES
2
k 2
q 3
NO
Статистика успешных решений по компиляторам
 Кол-во
С++3