No.2307 [Cherry 5 th Tune *] Cool 46
Story
This is a single game machine installed in a certain family restaurant, named "Cool 46".
Legendary records are born on this machine day after day.
Keep eating cards in style, and carve your name into the history of Cool records!!
Problem Statement
Cherry-chan has $N$ red cards and $M$ blue cards.
Each of the $(N+M)$ cards has $1$ integer written on it: the $i~(1 \leq i \leq N)$-th red card has $A_i$ written on it, and the $j~(1 \leq j \leq M)$-th blue card has $B_j$ written on it.
Here, $A_1,A_2, \dots, A_N$ are all distinct. Likewise, $B_1,B_2 \dots, B_M$ are all distinct.
Cherry-chan wants to eat all $(N+M)$ cards she has in the following way.
- First, she chooses any $1$ card among the cards she has and eats the chosen card.
- After that, she repeatedly chooses $1$ card that has the same color as, or the same integer written on it as, the card she ate immediately before, and eats the chosen card.
If Cherry-chan manages to eat all $(N+M)$ cards, she obtains a coolness determined as follows.
- Among the $(N+M)$ cards Cherry-chan ate, the number of times the color of the eaten card differs from the color of the card eaten immediately before it is the coolness.
- Strictly speaking, letting $C_k$ be the color of the $k~(1 \leq k \leq N+M)$-th card eaten, it is defined as the number of integers $k$ between $2$ and $(N+M)$, inclusive, such that $C_{k-1} \neq C_k$.
Can Cherry-chan eat all $(N+M)$ cards? If possible, give one order of eating the $(N+M)$ cards that maximizes the coolness she obtains.
Solve $T$ test cases.
Constraints
- $1 \leq T \leq 10^5$.
- Constraints for each test case
- $0 \leq N$.
- $0 \leq M$.
- $1 \leq N+M$.
- $1 \leq A_i \leq 10^9$.
- $1 \leq B_j \leq 10^9$.
- $A_1, A_2, \dots, A_N$ are all distinct.
- $B_1, B_2, \dots, B_M$ are all distinct.
- Constraints for each test file
- The sum of $(N+M)$ over the $T$ test cases is at most $2 \times 10^5$.
- All input values are integers.
Input
The input is given from standard input. The $1$-st line of the input is as follows.$T$Then, $T$ test cases follow. Each test case is given in the following format.
$N$ $M$ $A_1$ $A_2$ $\cdots$ $A_N$ $B_1$ $B_2$ $\cdots$ $B_M$
Output
For each test case, in the order given, output in the following format.
- If it is impossible for Cherry-chan to eat all $(N+M)$ cards: print
Noon $1$ line. - If it is possible for Cherry-chan to eat all $(N+M)$ cards: in the way of eating the $(N+M)$ cards that you give, which must maximize the coolness obtained, let $\textrm{Card}_k$ be the $k$-th card eaten, and output in the following format.
Yes $\textrm{Card}_1$ $\textrm{Card}_2$ $\vdots$ $\textrm{Card}_{N+M}$Here, output $\textrm{Card}_k$ in the following format.- If $\textrm{Card}_k$ is a red card with the integer $X$ written on it
Red $X$
- If $\textrm{Card}_k$ is a blue card with the integer $X$ written on it
Blue $X$
$X$ is not the index of the card within its color.
If there are multiple ways of eating the $(N+M)$ cards that maximize the coolness obtained, you may give any one of them.
- If $\textrm{Card}_k$ is a red card with the integer $X$ written on it
Do not forget the newline at the end.
Sample
Sample 1
Input
4 3 2 1 2 3 3 2 1 1 35 19 0 1 20230519 4 0 314 172 934 834
Output
Yes Red 1 Red 2 Blue 2 Blue 3 Red 3 No Yes Blue 20230519 Yes Red 172 Red 834 Red 314 Red 934
- [Test case $1$] If the $5$ cards are eaten in the order shown in the sample output, the colors of the $2$-nd and $3$-rd cards eaten differ, and so do the colors of the $4$-th and $5$-th cards eaten, so the coolness obtained is $2$.
Moreover, no order of eating the cards can yield a coolness greater than $2$, so this output is correct.
Note that obtaining coolness requires eating all $(N+M)$ cards. - [Test case $2$] Cherry-chan cannot eat all $(N+M)$ cards no matter what she does.
- [Test case $3$] She has only $1$ card, and if she manages to eat all the cards, the coolness obtained is $0$, since there is no integer that is at least $2$ and at most $1$.
- [Test case $4$] All the cards she has may be of the same color.
If there exists a way to eat the $(N+M)$ cards, any way of eating that maximizes the coolness will be judged correct. For example, for test case $1$, the following output is also correct.
Yes Blue 3 Red 3 Red 1 Red 2 Blue 2
Sample 2
Input
1 46 46 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
Output
Yes Red 1 Blue 1 Blue 2 Red 2 Red 3 Blue 3 Blue 4 Red 4 Red 5 Blue 5 Blue 6 Red 6 Red 7 Blue 7 Blue 8 Red 8 Red 9 Blue 9 Blue 10 Red 10 Red 11 Blue 11 Blue 12 Red 12 Red 13 Blue 13 Blue 14 Red 14 Red 15 Blue 15 Blue 16 Red 16 Red 17 Blue 17 Blue 18 Red 18 Red 19 Blue 19 Blue 20 Red 20 Red 21 Blue 21 Blue 22 Red 22 Red 23 Blue 23 Blue 24 Red 24 Red 25 Blue 25 Blue 26 Red 26 Red 27 Blue 27 Blue 28 Red 28 Red 29 Blue 29 Blue 30 Red 30 Red 31 Blue 31 Blue 32 Red 32 Red 33 Blue 33 Blue 34 Red 34 Red 35 Blue 35 Blue 36 Red 36 Red 37 Blue 37 Blue 38 Red 38 Red 39 Blue 39 Blue 40 Red 40 Red 41 Blue 41 Blue 42 Red 42 Red 43 Blue 43 Blue 44 Red 44 Red 45 Blue 45 Blue 46 Red 46
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
Kazun