Alice's Adventures in Cards
Contest: Codeforces Round 986 (Div. 2)
Difficulty rating: 2000
Tags: constructive algorithms, data structures, dp, graphs, greedy, implementation, ternary search

Alice is playing cards with the Queen of Hearts, King of Hearts, and Jack of Hearts. There are $$$n$$$ different types of cards in their card game. Alice currently has a card of type $$$1$$$ and needs a card of type $$$n$$$ to escape Wonderland. The other players have one of each kind of card.

In this card game, Alice can trade cards with the three other players. Each player has different preferences for the $$$n$$$ types of cards, which can be described by permutations$$$^{\text{∗}}$$$ $$$q$$$, $$$k$$$, and $$$j$$$ for the Queen, King, and Jack, respectively.

A player values card $$$a$$$ more than card $$$b$$$ if for their permutation $$$p$$$, $$$p_a > p_b$$$. Then, this player is willing to trade card $$$b$$$ to Alice in exchange for card $$$a$$$. Alice's preferences are straightforward: she values card $$$a$$$ more than card $$$b$$$ if $$$a > b$$$, and she will also only trade according to these preferences.

Determine if Alice can trade up from card $$$1$$$ to card $$$n$$$ subject to these preferences, and if it is possible, give a possible set of trades to do it.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$2\le n\le 2\cdot 10^5$$$) — the number of card types.

The next three lines contain the preferences of the Queen, King, and Jack respectively. Each of these lines contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1\le p_i\le n$$$) — a permutation corresponding to the player's preferences.

The sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output format:
For each test case, on the first line output a single string "YES" or "NO" (without the quotes) denoting whether Alice can trade up to card $$$n$$$.

If the first line was "YES", then on the next line output $$$k$$$ — the number of trades Alice will make. On the next $$$k$$$ lines output space separated a character $$$c\in \{\texttt{q}, \texttt{k}, \texttt{j}\}$$$ and integer $$$x$$$, denoting that Alice trades with player $$$c$$$ to get card $$$x$$$. It must be the case that on the $$$k$$$'th line, $$$x = n$$$. If there are multiple solutions, print any of them.

You can output this answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses. The same goes for the character $$$c$$$ denoting the player in the trade ($$$\texttt{Q}, \texttt{K}, \texttt{J}$$$ will all be accepted alongside their lowercase variants).

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first testcase, Alice can trade with the King to get card $$$2$$$. She can then trade with the Queen to get card $$$3$$$.

In the second testcase, even though Alice can trade with the Queen to get card $$$3$$$, with the King to get card $$$2$$$, and then with the Jack to get card $$$4$$$, this is not a valid solution since it doesn't respect Alice's preferences. We can show that there is no way for Alice to get to card $$$4$$$.

Example input:
2
3
1 3 2
2 1 3
1 2 3
4
2 3 1 4
1 2 3 4
1 4 2 3

Example output:
YES
2
k 2
q 3
NO

Editorial:
We will use DP to answer the following question for each $$$a$$$ from $$$n$$$ down to $$$1$$$: is it possible to trade up from card $$$a$$$ to card $$$n$$$?
To answer this question efficiently, we need to determine for each of the three players whether there exists some $$$b > a$$$ such that $$$p(b) < p(a)$$$ and it is possible to trade up from card $$$b$$$ to card $$$n$$$. We can do this efficiently by keeping track for each player the minimum value $$$x = p(b)$$$ over all $$$b$$$ that can reach $$$n$$$: then, for a given $$$a$$$ we can check for each player if $$$p(a)$$$ exceeds $$$x$$$. If it does for some player, we can then update the values $$$x$$$ for each of the three players. Alongside these minimum values $$$x$$$ we can keep track of the $$$b$$$ achieving them to be able to reconstruct a solution.
This takes time $$$O(n)$$$ since each iteration takes time $$$O(1)$$$.