It's easier to think about this problem if instead of thinking about which foot we're standing on, we consider the path length. You'll end on your left foot (the same one you started with) if the path contains an even number of edges, and on your right foot if it contains an odd number of edges. So really we care only about path lengths modulo \(2\).

If you're familiar with graph theory, you'll know it's difficult to efficiently answer shortest path queries between nodes in a general graph. This gives a hint that we probably can't and won't need to find our friends' path to solve this problem, reducing the space of possible approaches a fair bit.

Consider a tree. Notice that given two nodes, all possible paths (simple or non-simple) between them will have the same parity. Every edge will be traveled an odd number of times if it's on the simple path between those two nodes, or an even number of times if it's not on that simple path. So if the problem were given on a tree, then we'd have a solution: the answer is always impossible. In fact, it's even impossible on bipartite graphs, as if the graph is two-colorable, then each color represents the only foot that could ever touch that node.

When *is* it possible to get a path with different parity? Consider a graph consisting of only a cycle of odd length. Between any pair of nodes, there will have one even length path, and one odd length path. One will be shorter, the other will be longer. Furthermore, notice that the longer path will never repeat any edge, *meaning that here we know the answer is \(0\) even without knowing the distance between the nodes!*

In general, we'll want to consider the bridge-block tree (a.k.a. bridge-tree) of the given graph. That is, find all the [bridges](https://en.wikipedia.org/wiki/Bridge\_(graph_theory)), and condense each maximal component without bridges into a single node (the block, or \(2\)-edge-connected component). This can be done in \(\mathcal{O}(N+M)\) using Tarjan's bridge-finding algorithm. We'll be left with a tree where the only edges are bridges. These bridges are the only possible edges we might need to walk multiple times. (Why? By the definition of a bridge, everything else is part of a \(2\)-edge-connected component, meaning no matter where we want to go, there's one path there and a completely disjoint path back)

Our path from \(a_i\) to \(b_i\) therefore will always be: take some (possibly empty) part of the direct path from \(a_i\) to \(b_i\), then take some path to a block with an odd cycle, then take a path back to where you were, then finish the path from \(a_i\) to \(b_i\). Of all odd cycle blocks we could visit, we'll want to pick one which is the fewest bridges away from the direct path between \(a_i\) to \(b_i\). That number of bridges is what we'll add to our answer.

Famously, it can be shown that a graph is bipartite if and only if it contains no odd cycles. So, after finding each block, we'll first mark if it has an odd cycle by trying to \(2\)-color it using DFS. Then, we can find the distance from each block to the nearest odd cycle block using a single multi-source BFS (initializing the queue with all the odd cycle blocks and expanding outwards).

Finally, given two query nodes \(a_i\) and \(b_i\), we'll look up their blocks, then do a path-min query, getting the minimum "distance to odd cycle block" across every block on the direct path. Path-min queries on a tree can be handled in \(\mathcal{O}(\log N\)\) using binary-lifting, heavy-light decomposition, or a link-cut tree. The overall running time will be \(\mathcal{O}(N + M + Q \log N)\).