問題一覧 > 通常問題

No.2307 [Cherry 5 th Tune *] Cool 46

レベル : / AI推定難易度 : 1450 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 96
作問者 : 👑 Kazun / テスター : t98slider
お気に入りにしたユーザー ProblemId : 6002 / 自分の提出
問題文最終更新日: 2023-05-20 00:16:33
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 389 (Until that day when "Cherry Month" is over.) (順位表) の他の問題:

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 No on $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.

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もしくは右上の雲マークをクリックしてアカウントを作成してください。