Colored Portals
Contest: Educational Codeforces Round 169 (Rated for Div. 2)
Difficulty rating: 1600
Tags: binary search, brute force, data structures, graphs, greedy, implementation, shortest paths

There are $$$n$$$ cities located on a straight line. The cities are numbered from $$$1$$$ to $$$n$$$.

Portals are used to move between cities. There are $$$4$$$ colors of portals: blue, green, red, and yellow. Each city has portals of two different colors. You can move from city $$$i$$$ to city $$$j$$$ if they have portals of the same color (for example, you can move between a "blue-red" city and a "blue-green" city). This movement costs $$$|i-j|$$$ coins.

Your task is to answer $$$q$$$ independent queries: calculate the minimum cost to move from city $$$x$$$ to city $$$y$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — the number of cities and the number of queries, respectively.

The second line contains $$$n$$$ strings of the following types: BG, BR, BY, GR, GY, or RY; the $$$i$$$-th of them describes the portals located in the $$$i$$$-th city; the symbol B indicates that there is a blue portal in the city, G — green, R — red, and Y — yellow.

The $$$j$$$-th of the next $$$q$$$ lines contains two integers $$$x_j$$$ and $$$y_j$$$ ($$$1 \le x_j, y_j \le n$$$) — the description of the $$$j$$$-th query.

Additional constraints on the input:

- the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$;
- the sum of $$$q$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each query, print a single integer — the minimum cost to move from city $$$x$$$ to city $$$y$$$ (or $$$-1$$$ if it is impossible).

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
2
4 5
BR BR GY GR
1 2
3 1
4 4
1 4
4 2
2 1
BG RY
1 2

Example output:
1
4
0
3
2
-1

Editorial:
If cities $$$x$$$ and $$$y$$$ have a common portal, then the cost of the path is $$$|x-y|$$$.
Otherwise, we have to move from city $$$x$$$ to some intermediate city $$$z$$$. It's important to note that the type of city $$$z$$$ should be different from the type of city $$$x$$$. Otherwise, we could skip city $$$z$$$ and go directly from $$$x$$$ to the next city in the path. Since the type of city $$$z$$$ doesn't match the type of city $$$x$$$, it must have a common portal with city $$$y$$$. Therefore, the optimal path look like this: $$$x \rightarrow z \rightarrow y$$$. Additional cities won't decrease the cost of the path.
Now we have to figure out how to choose city $$$z$$$ to minimize the cost of the path. Without loss of generality, let's say that $$$x \le y$$$. Then there are three possible locations for city $$$z$$$:
• $$$z < x$$$, then the cost of the path is $$$(x-z) + (y-z)$$$;
• $$$x \le z \le y$$$, then the cost of the path is $$$(z-x) + (y-z) = y - x$$$;
• $$$y < z$$$, then the cost of the path is $$$(z-x) + (z-y)$$$.
It is easy to see that in each case, to minimize the cost of the path, we should choose $$$z$$$ as close to $$$x$$$ as possible.
Let's define two arrays: $$$\mathrm{lf}_{i, j}$$$ — the index of the nearest city to the left of $$$i$$$ with type $$$j$$$, and similarly $$$\mathrm{rg}_{i, j}$$$ — the index of the nearest city to the right of $$$i$$$ with type $$$j$$$.
Then the answer to the problem is the minimum value among $$$|x - \mathrm{lf}_{x, j}| + |\mathrm{lf}_{x, j} - y|$$$ and $$$|x - \mathrm{rg}_{x, j}| + |\mathrm{rg}_{x, j} - y|$$$ for all types $$$j$$$ for which there are common portals with cities $$$x$$$ and $$$y$$$.