CF2028D Alice's Adventures in Cards

Alice 正在和红心皇后、红心国王以及红心杰克玩纸牌游戏。这个游戏中有 $ n $ 种不同的纸牌类型。Alice 手上现在有一张类型为 $ 1 $ 的纸牌，她需要通过一系列的交换，得到类型为 $ n $ 的纸牌，才能逃出仙境。而其他三名玩家手上各自持有每种类型的纸牌一张。 在这个游戏中，Alice 可以与这些玩家进行纸牌交换。每位玩家对不同类型纸牌的偏好用排列 $ q $、$ k $ 和 $ j $ 来表示，分别对应红心皇后、红心国王和红心杰克。 对于任意玩家，如果在他们的排列 $ p $ 中，满足 $ p_a > p_b $ ，那么该玩家就认为类型为 $ a $ 的纸牌比类型为 $ b $ 的更有价值。于是，他们愿意用类型为 $ b $ 的纸牌换取类型为 $ a $ 的纸牌。而 Alice 的偏好简单直观：纸牌类型 $ a $ 比类型 $ b $ 更有价值，当且仅当 $ a > b $ ，并且她只会按照这种偏好进行交换。 请判断 Alice 能否通过与其他玩家的交换，从类型为 $ 1 $ 的纸牌升级到类型为 $ n $ 的纸牌。如果可以，请给出可能的交换方案。 $ ^{\text{∗}} $ 长度为 $ n $ 的排列是一个包含 $ n $ 个不同整数（从 $ 1 $ 到 $ n $）的数组。例如，$ [2,3,1,5,4] $ 是一个排列，但 $ [1,2,2] $ 和 $ [1,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" 来表示 Alice 是否能通过交换得到类型为 $ n $ 的纸牌。 如果可以输出 "YES"，接下来一行输出一个整数 $ k $ ，表示 Alice 将进行的交换次数。随后的 $ k $ 行，每行描述一次交换，以一个字符 $ c \in \{\texttt{q}, \texttt{k}, \texttt{j}\} $ 和一个整数 $ x $ 的形式出现，表示 Alice 与玩家 $ c $ 进行交换，以获得类型为 $ x $ 的纸牌。最终必须确保在第 $ k $ 次交换后，得到的纸牌为类型 $ n $。如果存在多种解决方案，输出任意一个即可。 输出中的字母大小写不固定。例如，"yEs"、"yes"、"Yes" 和 "YES" 都被视为肯定回答。同样，代表玩家的字符 $ c $ 也可以使用大写形式（$\texttt{Q}$、$\texttt{K}$、$\texttt{J}$）。

在第一个测试用例中，Alice 可以与红心国王交换以获得类型为 $ 2 $ 的纸牌，接着再与红心皇后交换以得到类型为 $ 3 $ 的纸牌。 在第二个测试用例中，尽管 Alice 能与红心皇后交换得到类型为 $ 3 $ 的纸牌，再接着与红心国王交换得到类型为 $ 2 $，最后与红心杰克交换得到类型为 $ 4 $ 的纸牌，但这种方案不符合 Alice 的偏好原则，因此无效。我们可以证明在这种情况下 Alice 无法获得类型为 $ 4 $ 的纸牌。 **本翻译由 AI 自动生成**