题目回顾

• 有 $4$ 种花色：C, D, H, S。
• 点数：2 ~ 9（共 $8$ 个等级）。
• 一种花色被选为 王牌花色（trump）。
• 每轮：第一名玩家出一张牌，第二名玩家必须出一张能 击败 它的牌。
• 击败规则：
  1. 同花色且点数更高；
  2. 或是 王牌花色 击败 非王牌花色（不论点数）。
• 已知 $n$ 轮结束后的 $2n$ 张牌（无序），要求构造一种可能的出牌顺序。
• 如果不可能，输出 "IMPOSSIBLE"。

---

核心思路

1. 分类处理

将牌按花色分成 $4$ 组，其中一组是王牌花色（记为 $T$），其余三组是非王牌花色。

对于 非王牌花色：

• 它们只能被两种方式击败：
  1. 同花色且点数更高的牌；
  2. 任意王牌花色的牌。

为了最小化对王牌花色的依赖，我们应当 尽可能在同花色内配对。

---

2. 同花色内配对

对于一种非王牌花色 $s$：

• 将它的牌按点数升序排序。
• 从最小到最大，相邻两张牌配对（点数大的击败点数小的）。
• 这样配对后，该花色最多剩下 1 张牌（如果该花色牌数为奇数）。

为什么这样最优？
因为如果跨点数配对，会导致更大的牌被浪费，无法让剩余牌更少，反而可能增加对王牌的依赖。

---

3. 处理剩余的牌

每种非王牌花色在内部配对后，可能剩下 $0$ 或 $1$ 张牌。
这些 剩余的非王牌牌 必须由 王牌花色 来击败（因为同花色内已经没有更大的牌可用了）。

设剩余的非王牌牌共有 $L$ 张，王牌花色共有 $M$ 张。

• 如果 $L > M$，则不可能，因为每张剩余的非王牌牌需要一张王牌来击败，但王牌不够。
• 否则，我们可以：
  • 用 $L$ 张王牌去击败这 $L$ 张剩余的非王牌牌（顺序任意）。
  • 剩下的 $M - L$ 张王牌花色的牌，它们之间可以 内部配对（点数大的击败点数小的），因为王牌也能被更大的王牌击败。

---

4. 构造输出

输出时：

• 先输出所有 非王牌花色内部配对（每对两张牌，第一张是被击败的，第二张是击败它的，但题目要求第一张是第一名玩家出的，第二张是第二名玩家击败它的——这里需要注意：
  在内部配对中，我们默认 点数小的先出，点数大的后出 即可满足击败规则）。
• 然后输出 王牌击败剩余非王牌 的配对。
• 最后输出 王牌内部剩余牌的配对。

最终按顺序每两行一组输出。

---

算法步骤（对应标程）

1. 读入 $n$ 和 $trump$ 花色。
2. 将 $2n$ 张牌按花色存入四个向量 bs[4]，点数转换为整数（'2' 对应 $0$，'9' 对应 $7$）。
3. 初始化结果向量 res 和剩余非王牌向量 left。
4. 对每种非王牌花色 $i \neq trump$：
   • 排序。
   • 如果牌数为奇数，把最大的一张放入 left（因为这张牌无法内部配对）。
   • 剩下的牌两两配对（点数小的先出，大的后出），存入 res。
5. 检查 left.size() 是否大于 bs[trump].size()：
   • 若是，输出 "IMPOSSIBLE"。
6. 否则：
   • 对 left 中的每张牌，用一张王牌（从 bs[trump] 中取最大的一张）击败它，存入 res。
   • 剩下的王牌花色的牌，两两配对（点数小的先出，大的后出），存入 res。
7. 按顺序每两行输出 res 中的牌对。

---

复杂度分析

• 每个测试用例：
  • 排序 $O(n \log n)$，其中 $n \le 16$，非常小。
  • 遍历和配对 $O(n)$。
• 总体 $O(t \cdot n \log n)$，完全可行。

---

举例验证（样例第一组）

输入：

3
S
3C 9S 4C 6D 3S 7S

• 王牌花色 = S。
• 牌：
  • C: 3C, 4C → 内部配对 (3C, 4C)
  • D: 6D → 剩余
  • H: 无
  • S: 9S, 3S, 7S

剩余非王牌：6D（1张）。
王牌牌：9S, 3S, 7S（3张）。
足够。

输出：

• 内部配对：3C 4C
• 王牌击败剩余：6D 9S
• 王牌内部配对：3S 7S

结果：

3C 4C
6D 9S
3S 7S

匹配样例。

---

总结

这个题的关键在于：

• 贪心：非王牌花色内部优先配对，减少对王牌的消耗。
• 奇数剩余处理：只留下最大的那张，因为这样最容易被王牌击败（其实这里留下的点数不重要，因为王牌无视点数击败非王牌）。
• 王牌内部再配对：最后剩下的王牌之间按点数大小配对。

标程巧妙地用 left 存储需要王牌击败的非王牌牌，然后依次处理，代码简洁高效。

#include <bits/stdc++.h>
 
#define long long long int
#define DEBUG
using namespace std;
 
// @author: pashka
 
int main() {
    ios::sync_with_stdio(false);
    
    int t;
    cin >> t;
    for (int tt = 0; tt < t; tt++) {
        int n;
        cin >> n;
    
        string suites = "CDHS";
    
        string ts;
        cin >> ts;
        int trump = suites.find(ts[0]);
    
        vector<int> bs[4];
        for (int i = 0; i < 2 * n; i++) {
            string s;
            cin >> s;
            bs[suites.find(s[1])].push_back(s[0] - '2');
        }
    
        vector<string> res;
        vector<string> left;
        for (int i = 0; i < 4; i++) {
            sort(bs[i].begin(), bs[i].end());
            if (i == trump) continue;
            if (bs[i].size() % 2 == 1) {
                int x = bs[i].back();
                left.push_back(string() + char('2' + x) + suites[i]);
                bs[i].pop_back();
            }
            for (int j = 0; j < (int) bs[i].size(); j++) {
                int x = bs[i][j];
                res.push_back(string() + char('2' + x) + suites[i]);
            }
        }
        if (left.size() > bs[trump].size()) {
            cout << "IMPOSSIBLE\n";
        } else {
            for (string s : left) {
                res.push_back(s);
                int x = bs[trump].back();
                bs[trump].pop_back();
                res.push_back(string() + char('2' + x) + suites[trump]);
            }
            for (int j = 0; j < (int) bs[trump].size(); j++) {
                int x = bs[trump][j];
                res.push_back(string() + char('2' + x) + suites[trump]);
            }
            for (int i = 0; i < 2 * n; i += 2) {
                cout << res[i] << " " << res[i + 1] << "\n";
            }
        }
    }
}