一、题目重述

有 $n$ 个城市排成一条直线，编号 $1$ 到 $n$。
每个城市拥有 $4$ 种颜色（B, G, R, Y）中的两种不同颜色，共有 $6$ 种可能的颜色组合：

• BG, BR, BY, GR, GY, RY

移动规则：可以从城市 $i$ 移动到城市 $j$，当且仅当它们有至少一种相同颜色，花费为 $|i-j|$。

回答 $q$ 个独立的询问：给定 $x, y$，求从 $x$ 到 $y$ 的最小花费，若不可达则输出 $-1$。

数据范围：

• $t \le 10^4$ 个测试用例
• 所有测试用例的 $n$ 之和 $\le 2 \times 10^5$
• 所有测试用例的 $q$ 之和 $\le 2 \times 10^5$
• $1 \le x, y \le n$

---

二、关键观察

2.1 直接移动的条件

设 $S_x$ 为城市 $x$ 拥有的颜色集合（$|S_x|=2$）。
若 $S_x \cap S_y \ne \varnothing$，则 $x$ 和 $y$ 可以直接移动，花费为：

$$\text{cost}_{\text{direct}} = |x - y|$$

这是理论下界，因为任何路径的花费 $\ge$ 直线距离（三角不等式）。

2.2 间接移动的路径结构

若 $S_x \cap S_y = \varnothing$，则需要经过一个中间城市 $z$，使得：

$$S_z \cap S_x \ne \varnothing \quad \text{且} \quad S_z \cap S_y \ne \varnothing $$

总花费为：

$$|x - z| + |z - y|$$

因为 $S_z$ 只有 $2$ 种颜色，且 $S_x$ 和 $S_y$ 不相交（共 $4$ 种不同颜色），所以 $S_z$ 必须恰好包含 $S_x$ 中的一种颜色和 $S_y$ 中的一种颜色。
因此，可能的 $S_z$ 有 $2 \times 2 = 4$ 种。

---

三、颜色编码与互补性质

将 $6$ 种颜色组合编码为 $0 \sim 5$：

组合	编码	包含颜色
BG	0	{B, G}
BR	1	{B, R}
BY	2	{B, Y}
GR	3	{G, R}
GY	4	{G, Y}
RY	5	{R, Y}

重要性质：两种颜色组合 $u$ 和 $v$ 有公共颜色 当且仅当 $u + v \ne 5$。

验证：

• $0+5=5$：BG 与 RY 无公共颜色 ✅
• $1+4=5$：BR 与 GY 无公共颜色 ✅
• $2+3=5$：BY 与 GR 无公共颜色 ✅
• 其他组合相加 $\ne 5$ 的都有公共颜色（例如 $0+1=1$：BG 与 BR 共有 B）

这个性质的由来：互补的两种组合正好覆盖全部 $4$ 种颜色且无交集。

因此：

$$\text{有公共颜色} \iff a[x] + a[y] \ne 5$$

---

四、预处理：最近的城市位置

我们需要快速回答：对于某个城市 $i$ 和某种颜色组合 $j$（$0 \le j \le 5$），离 $i$ 最近的、颜色组合为 $j$ 的城市在哪里？
分别考虑左边和右边。

4.1 左边最近 (lf)

定义 lf[i][j] 为：在 $i$ 左边（含 $i$ 本身）最近的、颜色组合为 $j$ 的城市下标（$0$-based）。若不存在，设为 $-\infty$。

预处理方法（正向扫描）：

vector<int> last(6, -INF);
for (int i = 0; i < n; ++i) {
    last[a[i]] = i;
    lf[i] = last;  // 复制数组
}

4.2 右边最近 (rg)

定义 rg[i][j] 为：在 $i$ 右边（含 $i$ 本身）最近的、颜色组合为 $j$ 的城市下标。若不存在，设为 $+\infty$。

预处理方法（反向扫描，或反转数组后正向扫描再反转）：

vector<int> last(6, INF);
for (int i = n-1; i >= 0; --i) {
    last[a[i]] = i;
    rg[i] = last;
}

标程中用了反转数组的技巧，效果等价。

---

五、询问处理

给定 $x, y$（已转为 $0$-based），我们想求最小花费。

5.1 枚举中间城市颜色

我们枚举所有可能的中间城市颜色 $j$（$0 \le j \le 5$），但必须满足：

• $j$ 与 $a[x]$ 有公共颜色 $\iff a[x] + j \ne 5$
• $j$ 与 $a[y]$ 有公共颜色 $\iff a[y] + j \ne 5$

同时满足这两个条件的 $j$ 就是合法的中间城市颜色。

5.2 使用预处理的最近位置

对于合法的 $j$，我们取 $x$ 左边最近的 $j$ 颜色城市 $z_l = lf[x][j]$ 和右边最近的 $j$ 颜色城市 $z_r = rg[x][j]$（如果存在）。

计算花费：

$$\text{cost}_l = |x - z_l| + |z_l - y|,\quad \text{cost}_r = |x - z_r| + |z_r - y| $$

取所有合法 $j$ 对应的这些值的最小值。

5.3 为什么只检查 $x$ 附近的 $j$ 城市？

正确性证明（简要）：

考虑最优路径 $x \to z \to y$，其中 $z$ 的颜色为 $j$。

• 如果 $z \le x$，那么 $lf[x][j]$ 是 $\le x$ 的最大的 $j$ 颜色城市，因此 $lf[x][j] \ge z$。
  由三角不等式：$$|x - lf| + |lf - y| \le |x - z| + |z - lf| + |lf - y| = |x - z| + |z - y| $$因为 $|z - lf| + |lf - y| \ge |z - y|$ 且 $|x - lf| \le |x - z|$，实际上需要更细致的分析，但已知结论是：用最近的那个替换 $z$ 不会增加总距离。严格证明需要分情况讨论，但这是 Codeforces 官方解法，已被验证正确。
• 如果 $z \ge x$，同理考虑 $rg[x][j]$。

因此，只需检查 $x$ 左右最近的 $j$ 城市即可。

5.4 直接移动的情况

当 $a[x] + a[y] \ne 5$ 时，$x$ 和 $y$ 本身就可以直接移动。
此时，取 $j = a[y]$，那么 $lf[x][j]$ 可能等于 $y$ 或某个更近的点，但计算出的 $|x - z| + |z - y|$ 的最小值恰好是 $|x - y|$（当 $z = y$ 时）。
所以枚举过程自动覆盖了直接移动的情况，无需额外判断。

---

六、算法步骤总结

1. 编码：将 $6$ 种颜色组合映射到 $0 \sim 5$，利用互补和为 $5$ 的性质。
2. 预处理：
   • 正向扫描，计算 lf[i][j]：$i$ 左边（含）最近的 $j$ 颜色城市下标。
   • 反向扫描，计算 rg[i][j]：$i$ 右边（含）最近的 $j$ 颜色城市下标。
3. 处理询问：
   • 枚举 $j = 0 \dots 5$，若 $a[x] + j \ne 5$ 且 $a[y] + j \ne 5$：
     • 若 $lf[x][j]$ 存在（$> -\infty$），更新答案 min(ans, |x - lf| + |lf - y|)
     • 若 $rg[x][j]$ 存在（$< \infty$），更新答案 min(ans, |x - rg| + |rg - y|)
   • 若答案仍为无穷大，输出 $-1$；否则输出答案。

---

七、复杂度分析

• 预处理：$O(n \cdot 6) = O(n)$
• 每个询问：枚举 $6$ 个 $j$，常数次操作，$O(1)$
• 总复杂度：$O(n + q)$ 每个测试用例，所有测试用例总和 $O(2\times10^5)$，非常高效。

---

八、完整代码（带详细注释）

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

const int INF = 1e9;
// 6 种颜色组合的编码顺序
const string vars[] = {"BG", "BR", "BY", "GR", "GY", "RY"};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    while (t--) {
        int n, q;
        cin >> n >> q;
        
        vector<int> a(n);  // 每个城市的颜色组合编码 0..5
        for (int i = 0; i < n; ++i) {
            string s;
            cin >> s;
            a[i] = find(vars, vars + 6, s) - vars;
        }
        
        // lf[i][j] : i 左边（含）最近的 j 颜色城市下标，不存在为 -INF
        // rg[i][j] : i 右边（含）最近的 j 颜色城市下标，不存在为 INF
        vector<vector<int>> lf(n), rg(n);
        
        // 正向扫描，计算左边最近
        vector<int> last(6, -INF);
        for (int i = 0; i < n; ++i) {
            last[a[i]] = i;
            lf[i] = last;  // 复制数组
        }
        
        // 反向扫描，计算右边最近
        // 标程用了反转数组的技巧，这里直接反向扫描更直观
        vector<int> last2(6, INF);
        for (int i = n - 1; i >= 0; --i) {
            last2[a[i]] = i;
            rg[i] = last2;
        }
        
        while (q--) {
            int x, y;
            cin >> x >> y;
            --x; --y;  // 转为 0-based
            
            int ans = INF;
            // 枚举中间城市的颜色组合 j
            for (int j = 0; j < 6; ++j) {
                // j 必须与 x 有公共颜色 且 与 y 有公共颜色
                if (a[x] + j != 5 && a[y] + j != 5) {
                    // 检查 x 左边最近的 j 颜色城市
                    int z = lf[x][j];
                    if (z > -INF) {
                        ans = min(ans, abs(x - z) + abs(z - y));
                    }
                    // 检查 x 右边最近的 j 颜色城市
                    z = rg[x][j];
                    if (z < INF) {
                        ans = min(ans, abs(x - z) + abs(z - y));
                    }
                }
            }
            
            if (ans > INF / 2) ans = -1;
            cout << ans << '\n';
        }
    }
    
    return 0;
}

---

九、正确性总结

1. 直接移动：当 $a[x] + a[y] \ne 5$ 时，枚举到 $j = a[y]$ 就会得到 $z = y$，花费 $|x-y|$，是最优的。
2. 间接移动：当 $a[x] + a[y] = 5$ 时，必须经过中间城市。由于颜色组合只有 $6$ 种，我们枚举所有可能的 $j$，并利用预处理的最近位置，保证能找到最优的 $z$。因为最优的 $z$ 一定是离 $x$ 最近的某种 $j$ 颜色城市之一（否则可以用更近的替换而不增加总距离）。
3. 不可达：若没有任何合法 $j$ 使得存在 $z$，则输出 $-1$。