← 返回题目列表

Codeforces · 2028/D

D. 爱丽丝纸牌历险记

中文机器翻译题面 查看原题

Alice 正在与红心皇后、红心国王和红心杰克打牌。他们的纸牌游戏中有 $$$n$$$ 不同类型的纸牌。 Alice 目前拥有一张类型为 $$$1$$$ 的卡,并且需要一张类型为 $$$n$$$ 的卡才能逃离仙境。其他玩家各有一张牌。

在这个纸牌游戏中,爱丽丝可以与其他三名玩家交换纸牌。每个玩家对 $$$n$$$ 类型的牌有不同的偏好,可以通过排列 $$$^{\text{∗}}$$$ $$$q$$$、$$$k$$$ 和 $$$j$$$ 分别描述皇后、国王和杰克。

如果对于其排列$$$p$$$,$$$p_a > p_b$$$,则玩家对牌$$$a$$$的重视程度高于牌$$$b$$$。然后,该玩家愿意将卡 $$$b$$$ 交易给 Alice,以换取卡 $$$a$$$。 Alice 的偏好很简单:如果 $$$a > b$$$,她对卡 $$$a$$$ 的重视程度高于卡 $$$b$$$,并且她也只会根据这些偏好进行交易。

确定 Alice 是否可以根据这些偏好从卡 $$$1$$$ 升级到卡 $$$n$$$,如果可能,请给出一组可能的交易来完成此操作。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$ 行中,输出空格分隔了 \{\texttt{q}、\texttt{k}、\texttt{j}\}$$$ 中的字符 $$$c\ 和整数 $$$x$$$,表示 Alice 与玩家 $$$c$$$ 交易以获得卡 $$$x$$$。情况一定是,在第 $$$k$$$ 行,$$$x = n$$$。如果有多个解决方案,请打印其中任何一个。

您可以在任何情况下(大写或小写)输出此答案。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定响应。对于表示交易中的玩家的字符 $$$c$$$ 也是如此($$$\texttt{Q}、\texttt{K}、\texttt{J}$$$ 都将与其小写变体一起被接受)。

示例

输入 #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

输出 #1

YES
2
k 2
q 3
NO

注意

在第一个测试用例中,Alice 可以与 King 交易以获得卡 $$$2$$$。然后她可以与女王交易以获得卡 $$$3$$$。

在第二个测试用例中,即使 Alice 可以与 Queen 交易以获得卡 $$$3$$$,与 King 交易以获得卡 $$$2$$$,然后与 Jack 交易以获得卡 $$$4$$$,但这不是一个有效的解决方案,因为它不尊重 Alice 的偏好。我们可以证明 Alice 无法到达卡 $$$4$$$。