← 返回题目列表

Codeforces · 2004/D

D. 彩色门户

中文机器翻译题面 查看原题

有 $$$n$$$ 个城市位于一条直线上。城市编号从 $$$1$$$ 到 $$$n$$$。

门户用于在城市之间移动。门户有 $$$4$$$ 颜色:蓝色、绿色、红色和黄色。每个城市都有两种不同颜色的门户。如果城市 $$$i$$$ 具有相同颜色的传送门,您可以从城市 $$$i$$$ 移动到城市 $$$j$$$(例如,您可以在“蓝红色”城市和“蓝绿色”城市之间移动)。此动作需要花费 $$$|i-j|$$$ 硬币。

你的任务是回答 $$$q$$$ 独立查询:计算从城市 $$$x$$$ 移动到城市 $$$y$$$ 的最低成本。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) - 分别是城市数量和查询数量。

第二行包含以下类型的 $$$n$$$ 字符串:BG、BR、BY、GR、GY 或 RY;其中第 $$$i$$$ 描述了位于第 $$$i$$$ 城市的门户;符号B表示城市中有一个蓝色的传送门,G——绿色,R——红色,Y——黄色。

接下来的 $$$q$$$ 行的第 $$$j$$$ 行包含两个整数 $$$x_j$$$ 和 $$$y_j$$$ ($$$1 \le x_j, y_j \le n$$$) - 第 $$$j$$$ 查询的描述。

输入的附加限制:

- 所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$;
- 所有测试用例的 $$$q$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个查询,打印一个整数 - 从城市 $$$x$$$ 移动到城市 $$$y$$$ 的最低成本(如果不可能,则打印 $$$-1$$$)。

示例

输入 #1

2
4 5
BR BR GY GR
1 2
3 1
4 4
1 4
4 2
2 1
BG RY
1 2

输出 #1

1
4
0
3
2
-1