311089: CF1932D. Card Game
Description
Two players are playing an online card game. The game is played using a 32-card deck. Each card has a suit and a rank. There are four suits: clubs, diamonds, hearts, and spades. We will encode them with characters 'C', 'D', 'H', and 'S', respectively. And there are 8 ranks, in increasing order: '2', '3', '4', '5', '6', '7', '8', '9'.
Each card is denoted by two letters: its rank and its suit. For example, the 8 of Hearts is denoted as 8H.
At the beginning of the game, one suit is chosen as the trump suit.
In each round, players make moves like this: the first player places one of his cards on the table, and the second player must beat this card with one of their cards. After that, both cards are moved to the discard pile.
A card can beat another card if both cards have the same suit and the first card has a higher rank than the second. For example, 8S can beat 4S. Additionally, a trump card can beat any non-trump card, regardless of the rank of the cards, for example, if the trump suit is clubs ('C'), then 3C can beat 9D. Note that trump cards can be beaten only by the trump cards of higher rank.
There were $n$ rounds played in the game, so the discard pile now contains $2n$ cards. You want to reconstruct the rounds played in the game, but the cards in the discard pile are shuffled. Find any possible sequence of $n$ rounds that might have been played in the game.
InputThe first line contains integer $t$ ($1 \le t \le 100$) — the number of test cases. Then $t$ test cases follow.
The first line of a test case contains the integer number $n$ ($1\le n\le 16$).
The second line of a test case contains one character, the trump suit. It is one of "CDHS".
The third line of a test case contains the description of $2n$ cards. Each card is described by a two-character string, the first character is the rank of the card, which is one of "23456789", and the second one is the suit of the card, which is one of "CDHS". All cards are different.
OutputFor each test case print the answer to it:
- Print $n$ lines. In each line, print the description of two cards, in the same format as in the input: the first card that was played by the first player, and then the card that was used by the second player to beat it.
- If there is no solution, print a single line "IMPOSSIBLE".
If there are multiple solutions, print any of them.
ExampleInput8 3 S 3C 9S 4C 6D 3S 7S 2 C 3S 5D 9S 6H 1 H 6C 5D 1 S 7S 3S 1 H 9S 9H 1 S 9S 9H 1 C 9D 8H 2 C 9C 9S 6H 8COutput
3C 4C 6D 9S 3S 7S IMPOSSIBLE IMPOSSIBLE 3S 7S 9S 9H 9H 9S IMPOSSIBLE 6H 9C 9S 8C
Output
在游戏开始时，选择一个花色作为“王牌”。
每一轮，玩家的行动如下：第一个玩家放下一张牌，第二个玩家必须用一张牌击败这张牌。之后，这两张牌都会被移到弃牌堆中。
一张牌可以击败另一张牌，如果两张牌花色相同且第一张牌的等级高于第二张。例如，"8S"可以击败"4S"。此外，王牌可以击败任何非王牌，不管牌的等级如何，例如，如果王牌是梅花("C")，那么"3C"可以击败"9D"。注意，只有更高等级的王牌才能击败王牌。
游戏中进行了n轮，所以弃牌堆现在有2n张牌。你想要重建游戏中的n轮，但是弃牌堆中的牌已经洗乱了。找出可能已经进行的n轮的任何可能的顺序。
输入数据格式：
- 第一行包含整数t（1≤t≤100），表示测试用例的数量。然后是t个测试用例。
- 每个测试用例的第一行包含整数n（1≤n≤16）。
- 每个测试用例的第二行包含一个字符，表示王牌的花色。它是"CDHS"中的一个。
- 每个测试用例的第三行包含2n张牌的描述。每张牌由一个两字符的字符串描述，第一个字符是牌的等级，它是"23456789"中的一个，第二个字符是牌的花色，它是"CDHS"中的一个。所有的牌都是不同的。
输出数据格式：
- 对于每个测试用例，输出它的答案：
- 打印n行。在每一行中，按输入格式打印两张牌的描述：第一张是第一个玩家出的牌，第二张是第二个玩家用来击败它的牌。
- 如果没有解决方案，打印单个词"IMPOSSIBLE"。
- 如果有多个解决方案，打印其中的任何一个。题目大意：这是一个两人在线牌类游戏，使用32张牌的牌组进行游戏。每张牌有一个花色和一个等级。有四种花色：梅花、方块、红心和黑桃，分别用字符'C'、'D'、'H'和'S'表示。共有8个等级，按升序排列为'2'、'3'、'4'、'5'、'6'、'7'、'8'、'9'。每张牌由两个字母表示：它的等级和花色。例如，红心8表示为"8H"。 在游戏开始时，选择一个花色作为“王牌”。 每一轮，玩家的行动如下：第一个玩家放下一张牌，第二个玩家必须用一张牌击败这张牌。之后，这两张牌都会被移到弃牌堆中。 一张牌可以击败另一张牌，如果两张牌花色相同且第一张牌的等级高于第二张。例如，"8S"可以击败"4S"。此外，王牌可以击败任何非王牌，不管牌的等级如何，例如，如果王牌是梅花("C")，那么"3C"可以击败"9D"。注意，只有更高等级的王牌才能击败王牌。 游戏中进行了n轮，所以弃牌堆现在有2n张牌。你想要重建游戏中的n轮，但是弃牌堆中的牌已经洗乱了。找出可能已经进行的n轮的任何可能的顺序。 输入数据格式： - 第一行包含整数t（1≤t≤100），表示测试用例的数量。然后是t个测试用例。 - 每个测试用例的第一行包含整数n（1≤n≤16）。 - 每个测试用例的第二行包含一个字符，表示王牌的花色。它是"CDHS"中的一个。 - 每个测试用例的第三行包含2n张牌的描述。每张牌由一个两字符的字符串描述，第一个字符是牌的等级，它是"23456789"中的一个，第二个字符是牌的花色，它是"CDHS"中的一个。所有的牌都是不同的。 输出数据格式： - 对于每个测试用例，输出它的答案： - 打印n行。在每一行中，按输入格式打印两张牌的描述：第一张是第一个玩家出的牌，第二张是第二个玩家用来击败它的牌。 - 如果没有解决方案，打印单个词"IMPOSSIBLE"。 - 如果有多个解决方案，打印其中的任何一个。