409025: GYM103416 E Circular Graph

You're given an undirected graph with $$$n$$$ nodes and $$$m + n$$$ edges ($$$m$$$ red and $$$n$$$ black edges). Nodes are numbered from $$$1$$$ to $$$n$$$ in the order around the circle. There are $$$n$$$ black edges between adjacent nodes. Nodes $$$i$$$ and $$$(i + 1)$$$ are adjacent for $$$(1 \le i \le n - 1)$$$, nodes $$$1$$$ and $$$n$$$ are also adjacent.

You are given $$$m$$$ red edges.

The path is considered valid if and only if the given path contains at most $$$1$$$ red edge.

Find the length of the shortest valid path between two vertices $$$a_i$$$ and $$$b_i$$$.

Solve this problem for $$$Q$$$ independent queries.

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$3 \le n \le 200\ 000$$$ and $$$0 \le m \le 200\ 000$$$).

The $$$i$$$-th of the next $$$m$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \neq v_i$$$), that mean that there's a red edge between nodes $$$u_i$$$ and $$$v_i$$$.

The next line contains one integer $$$Q$$$ ($$$1 \le Q \le 200\ 000$$$) - the number of queries. Each of the next $$$Q$$$ lines contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$a_i \neq b_i$$$).

For each query print the length of the shortest valid path between two vertices $$$a_i$$$ and $$$b_i$$$.

6 1
3 5
4
3 6
3 5
1 2
1 4

2
1
1
3

The graph of the first testcase