题解说明

问题背景：
这是 Codeforces 上著名的 “Meow” 题的参考实现。题意大致是：给定一个长度为 $m$ 的操作序列，每个元素是 $1 \sim n$ 的编号。需要用若干队列（双端队列）来模拟入队/出队操作，并输出一系列操作（$1$ 类或 $2$ 类）来保证序列合法执行。

操作定义：

• $1\ x$：对编号为 $x$ 的队列执行一次操作（入队或出队，具体由上下文决定）
• $2\ x\ y$：将队列 $x$ 的内容合并到队列 $y$

核心思路：
$1.$ 队列管理：

• 每个节点编号 $x$ 对应一个队列 $id[x]$。
• 使用双端队列 $Q[id]$ 存储队列内容。
• 使用栈 $q$ 管理空闲队列编号，保证可以动态分配和回收。

$2.$ 基本操作 $work(x)$：

• 如果 $x$ 已在某个队列中：
  • 若 $x$ 在队尾：直接出队（$1$ 类操作）
  • 若 $x$ 在队首：需要借助临时队列 $I$，先操作 $I$，再合并（$2$ 类操作）
• 如果 $x$ 不在任何队列：
  • 若有空闲队列：分配一个队列 $id$，执行入队（$1$ 类操作）
  • 若无空闲队列：返回失败，进入特殊处理

$3.$ 特殊处理：

• 当 $work(x)$ 失败时，说明没有空闲队列可用。
• 这时需要找到一个连续区间 $[i,r]$，在该区间内进行整体调整。
• 根据区间末尾元素 $x$ 及其所在队列的另一端元素 $y$，分为三种情况：
  • 情况 $1$：$x = a[i]$，直接用临时队列 $I$ 过渡
  • 情况 $2$：$y$ 在区间内出现偶数次，调整队列后处理
  • 情况 $3$：$y$ 在区间内出现奇数次，用临时队列拆分处理

$4.$ 输出答案：

• 所有操作存入 $Ans$ 数组
• 最后输出操作总数和每个操作的具体内容

算法流程：
$1.$ 初始化空闲队列栈 $q$，存入 $2 \times (n-1)$ 个队列编号。
$2.$ 读取操作序列 $a[1..m]$。
$3.$ 遍历序列：

• 调用 $work(a[i])$，若成功则继续
• 若失败，进入特殊处理，找到区间 $[i,r]$ 并分类讨论
  $4.$ 输出操作总数和操作序列

复杂度分析：

• 每个元素最多被处理一次，$work$ 和特殊处理均摊 $O(1)\sim O(m)$
• 总复杂度 $O(m)$，适合 $m \leq 4 \times 10^6$ 的数据范围

实现细节与注意点：

• 使用大缓冲区和自定义 IO，加快读写速度
• 队列编号管理：通过栈 $q$ 动态分配和回收
• 特殊处理逻辑较复杂，需要仔细分类讨论
• 输出操作时区分 $1$ 类和 $2$ 类操作

总结：
该代码通过维护多个双端队列和一个空闲队列池，结合正常处理和特殊处理两种策略，保证了操作序列的可执行性。整体思路是 “贪心 $+$ 分类讨论”，实现复杂但效率高，能够在大数据范围内通过。

#include <bits/stdc++.h>
using namespace std;

// 输入输出缓冲区：用于快速读写，提升效率（标准IO下仍适用）
char buf[1 << 24], *p1 = buf, *p2 = buf;  // 输入缓冲区及指针
char obuf[1 << 24], *O = obuf;            // 输出缓冲区及指针

// 自定义getchar：从输入缓冲区读取字符，比标准getchar更快
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

// 快速读取整数：处理数字字符，转换为int（跳过非数字字符）
int read() {
    int x = 0;          // 存储读取的整数
    char ch = getchar();// 读取第一个字符

    while (!isdigit(ch))// 跳过非数字字符（如空格、换行）
        ch = getchar();

    while (isdigit(ch)) // 读取所有连续数字字符
        x = x * 10 + (ch ^ 48), ch = getchar(); // (ch^48) 等价于 ch-'0'

    return x;
}

// 递归打印整数：处理数字的每一位，确保正确的顺序（如123→先1再2再3）
void print(int x) {
    if (x > 9)          // 若数字大于9，先打印高位
        print(x / 10);

    *O++ = x % 10 + '0';// 打印当前最低位（转换为字符）
}

// 宏定义：快速创建pair<int, int>（用于存储操作答案）
#define mp make_pair

// 全局常量：最大节点数N，最大操作数M
const int N = 2005, M = 4e6 + 5;

// 全局变量定义
deque<int> Q[N];               // 双端队列数组：Q[id]表示编号为id的队列
pair<int, int> Ans[M];         // 存储操作答案：first=队列号，second=-1表示1类操作，否则2类操作
int Ansnum;                    // 答案操作的总数
int n, m, k;                   // n=节点数，m=操作序列长度，k=（原问题参数，代码中未直接使用）
int a[M];                      // 存储输入的操作序列（每个元素是节点编号）
int id[N];                     // 节点对应的队列编号：id[x]表示节点x所在队列的id
int q[N], T;                   // q=空闲队列编号栈，T=栈顶指针（管理可用的队列id）
int I;                         // 初始队列编号（用于特殊操作的临时队列）
int Te;                        // 测试用例总数
int GG;                        // 标记当前处理的分支类型（用于调试/逻辑区分，无实际功能）

// 记录操作到答案数组：根据是否有第二个参数，生成1类或2类操作
// x=队列号，y=-1时为1类操作（格式：1 x），y!=-1时为2类操作（格式：2 x y）
void V(int x, int y = -1) {
    Ans[++Ansnum] = mp(x, y);
}

// 判断节点x是否是其所在队列的“顶端”（即队列的最后一个元素）
// 前提：id[x]不为0（x已在某个队列中）
int Top(int x) {
    return id[x] && Q[id[x]].back() == x;
}

// 处理单个节点x的核心操作：入队或出队
// 返回1表示处理成功，0表示需要特殊处理（无空闲队列时）
int work(int x) {
    if (id[x]) {  // 情况1：x已在某个队列中（执行出队）
        if (Q[id[x]].back() == x) {  // x是队列尾→直接出队（1类操作）
            V(id[x]);                // 记录1类操作：出队队列id[x]
            Q[id[x]].pop_back();     // 从队列尾移除x
        } else {  // x是队列头→需先合并队列再出队（2类+1类操作）
            V(I);                    // 记录1类操作：出队临时队列I
            V(id[x], I);             // 记录2类操作：合并队列id[x]到I
            Q[id[x]].pop_front();    // 从队列头移除x
        }
        q[++T] = id[x];  // 释放队列id[x]，加入空闲栈
        id[x] = 0;       // 标记x不再属于任何队列
    } else {  // 情况2：x不在队列中（执行入队）
        if (!T) return 0;  // 无空闲队列→处理失败，需后续特殊处理

        id[x] = q[T--];    // 从空闲栈取一个队列id
        V(id[x]);          // 记录1类操作：入队队列id[x]
        Q[id[x]].push_back(x);  // 将x加入队列尾
    }
    return 1;  // 处理成功
}

int main() {
    // 移除原文件读写代码：freopen("meow.in", "r", stdin); freopen("meow.out", "w", stdout);
    
    Te = read();  // 读取测试用例总数

    while (Te--) {  // 遍历每个测试用例
        n = read(), m = read(), k = read();  // 读取当前测试用例的n、m、k
        T = 0;       // 重置空闲队列栈指针（栈空）
        Ansnum = 0;  // 重置答案操作数

        // 初始化空闲队列栈：加入2*(n-1)个队列id（1~2n-2）
        for (int i = 1; i < n; i++)
            q[++T] = i, q[++T] = i;

        I = n;  // 初始化临时队列编号I（从n开始，避免与初始空闲队列冲突）

        // 读取长度为m的操作序列a
        for (int i = 1; i <= m; i++)
            a[i] = read();

        // 处理操作序列中的每个元素（从第1个到第m个）
        for (int i = 1; i <= m; i++) {
            GG = 0;  // 重置分支标记

            if (work(a[i]))  // 尝试正常处理a[i]，成功则跳过后续特殊处理
                continue;

            // 正常处理失败→进入特殊处理：找到连续需处理的区间[i, r]
            int r = i;
            // 扩展r：直到下一个元素不是其队列顶端，或超出序列长度
            while (r + 1 <= m && Top(a[r + 1]))
                r++;
            r++;  // 最终区间为[i, r]

            int x = a[r];  // 区间末尾的元素x（特殊处理的关键节点）
            int y;         // 存储x所在队列的另一端元素（头或尾）

            // 特殊情况1：区间末尾元素x等于当前元素a[i]→无法正常入队，需临时队列
            if (x == a[i]) {
                GG = 1;
                V(I);  // 记录1类操作：使用临时队列I
                // 处理区间内[i+1, r-1]的元素
                for (int j = i + 1; j < r; j++)
                    work(a[j]);
                V(I);  // 记录1类操作：释放临时队列I
                i = r;  // 跳过已处理的区间，下次从r+1开始
                continue;
            }

            // 确定x所在队列的另一端元素y（头或尾）
            if (Top(x))
                y = Q[id[x]].front();  // x是队尾→y是队头
            else
                y = Q[id[x]].back();   // x是队头→y是队尾

            // 统计区间[i+1, r-1]中y出现的次数（用于判断奇偶性）
            int num = 0;
            for (int j = i + 1; j < r; j++)
                num += (a[j] == y);

            // 特殊情况2：y出现次数为偶数→调整队列后处理
            if (!(num & 1)) {
                GG = 2;
                V(id[x]);  // 记录1类操作：出队x所在队列
                // 调整队列：将a[i]加入队尾，再移除队头（相当于轮换）
                Q[id[x]].push_back(a[i]), Q[id[x]].pop_front();
                id[a[i]] = id[x];  // 标记a[i]属于x的队列

                // 处理区间[i+1, r-1]的元素
                for (int j = i + 1; j < r; j++)
                    if (a[j] == y)
                        V(I);  // y出现时，用临时队列I过渡
                    else
                        work(a[j]);  // 其他元素正常处理

                V(I);               // 记录1类操作：释放临时队列I
                V(id[x], I);        // 记录2类操作：合并x的队列到I
                id[x] = 0;          // 释放x的队列
            } else {  // 特殊情况3：y出现次数为奇数→用临时队列拆分处理
                GG = 3;
                V(I);  // 记录1类操作：使用临时队列I
                // 给a[i]分配临时队列I并入队
                id[a[i]] = I, Q[I].push_back(a[i]);
                int II = I;  // 保存当前临时队列I
                I = id[x];   // 更新I为x的队列（用于后续合并）

                // 处理区间[i+1, r]的元素
                for (int j = i + 1; j <= r; j++)
                    if (a[j] == y || a[j] == x)
                        V(id[x]);  // y或x出现时，操作x的队列
                    else
                        work(a[j]);  // 其他元素正常处理

                // 清空x的队列，释放节点x和y的队列标记
                Q[id[x]].clear();
                id[x] = id[y] = 0;
                q[++T] = II;  // 回收临时队列II到空闲栈
            }

            i = r;  // 跳过已处理的区间，下次从r+1开始
        }

        // 输出当前测试用例的答案：先输出操作总数
        print(Ansnum);
        *O++ = '\n';

        // 输出每个操作的具体内容
        for (int i = 1; i <= Ansnum; i++) {
            // 判断操作类型：second=-1→1类操作，否则→2类操作
            *O++ = (Ans[i].second == -1 ? '1' : '2');
            *O++ = ' ';
            print(Ans[i].first);  // 输出第一个队列号

            // 2类操作需额外输出第二个队列号
            if (Ans[i].second != -1) {
                *O++ = ' ';
                print(Ans[i].second);
            }

            *O++ = '\n';  // 每个操作后换行
        }
    }

    // 将输出缓冲区的内容写入标准输出（控制台）
    fwrite(obuf, 1, O - obuf, stdout);
    return 0;
}