D. Цветные порталы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На прямой расположено $$$n$$$ городов. Города пронумерованы целыми числами от $$$1$$$ до $$$n$$$.

Для перемещения между городами используются порталы. Порталы бывают $$$4$$$ цветов: синий, зеленый, красный и желтый. В каждом городе расположены порталы двух разных цветов. Из города $$$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 — желтого.

$$$j$$$-я из следующих $$$q$$$ строк содержит два целых числа $$$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$$$, если это невозможно).

Пример
Входные данные
2
4 5
BR BR GY GR
1 2
3 1
4 4
1 4
4 2
2 1
BG RY
1 2
Выходные данные
1
4
0
3
2
-1