Problem: road_to_nutella (2023 practice)

You and your friends have drawn a really big connected graph in sidewalk chalk with \(N\) nodes (numbered from \(1..N\)) and \(M\) edges. \(Q\) times, there will be a race from node \(a_i\) to node \(b_i\)​, with a chance to win a coveted hazelnut chocolate snack. By the unbreakable rules of hop-scotch, everyone must travel along a path from node \(a_i\) to node \(b_i\) using edges in the graph, alternating which foot touches the ground at each node, starting each race with their left foot on \(a_i\).

Your friends will make a mad dash for the chocolate along the **shortest path** from \(a_i\) to \(b_i\)​. You on the other hand are looking for a more interesting challenge, and are allowed to take *any* path, potentially including any nodes (even \(b_i\)) multiple times. You want to end at node \(b_i\)​, but with the following conditions:
 - You must finish on a different foot from everyone who took the shortest path.
- To make things interesting, you'd like to minimize the number of edges you travel through more than once.

{{PHOTO_ID:903178538089777|WIDTH:600}}

*An illustration of the first sample. Your friends take a shortest path (blue), and you can take the path in red. The path in red travels through \(1\) edge multiple times: the edge connecting nodes \(6\) and \(8\).*

For each query, is it possible to fulfill your two conditions? If so, add the minimum number of edges you have to travel through multiple times to your answer. If not, add \(-1\) to your answer.

# Constraints

\(1 \leq T  \leq 140\)
\(1 \leq N, M, Q \leq 3*10^5\)

The sum of \(N\), \(M\), and \(Q\) over all cases are each no more than \(3*10^6\).
There will be at most one edge connecting the same pair of nodes directly.
The graph is connected.
No edge will connect a node with itself.
For all queries, \(a_i \neq b_i\). That is, the start and end of each race will be on different nodes.

# Input Format

Input begins with an integer \(T\), the number of test cases. For each test case, there is first a line containing two space-separated integers, \(N\) and \(M\). \(M\) lines follow, each containing two integers describing the endpoints of an edge. Then, there is a line containing a single integer \(Q\). \(Q\) lines follow, the \(i\)th of which contains two space-separated integers \(a_i\) and \(b_i\).

# Output Format

For the \(i\)th test case, print "`Case #i:` " followed by the sum of answers to all queries in that case. The answer to a query is the minimum number of edges you'd need to travel through more than once to reach node \(b_i\) on a the other foot than your friends, or \(-1\) if it isn't possible to do so.

# Sample Explanation

The graph for the first case is shown above. The first query asks us to go from node \(7\) to node \(1\). The shortest paths (one shown in blue) will start on the left and end on the right foot, but we can end our our left by taking the red path. We'll cross the edge from \(6\) to \(8\) more than once, so the answer to this query is \(1\). The answers to the queries are \([1, 0, 2, 0, 2]\) respectively.

In the second case, the query answers are \([-1, -1]\) respectively.

In the third case, the query answers are \([0, 0]\) respectively.

In the fourth case, the query answers are \([-1, -1]\) respectively.





Sample input:
4
13 15
1 2
2 3
2 4
4 5
3 5
5 6
6 7
6 8
8 9
8 12
8 13
9 10
10 11
11 12
12 13
5
7 1
7 8
1 2
1 11
2 3
4 3
1 2
2 3
2 4
2
2 3
1 4
4 4
1 2
2 3
1 3
3 4
2
2 3
1 4
4 4
1 2
2 3
1 4
3 4
2
2 3
1 4


Sample output:
Case #1: 5
Case #2: -2
Case #3: 0
Case #4: -2


Solution: 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)\).


Code: #include <algorithm>
#include <iostream>
#include <queue>
#include <set>
#include <vector>
using namespace std;

const int INF = (int)1e9, lgmax = 20;

int N, M, Q;
vector<vector<int>> adj, block_adj;

// Start of bridge-finding code.

int timer, nblocks;
vector<bool> visit;
vector<int> lowlink, tin, stack, block;
vector<vector<int>> blocks;
set<pair<int, int>> bridges;

void dfs(int u, int p) {
  visit[u] = true;
  lowlink[u] = tin[u] = timer++;
  stack.push_back(u);
  int children = 0;
  for (int v : adj[u]) {
    if (v == p) {
      continue;
    }
    if (visit[v]) {
      lowlink[u] = min(lowlink[u], tin[v]);
    } else {
      dfs(v, u);
      lowlink[u] = min(lowlink[u], lowlink[v]);
      if (lowlink[v] > tin[u]) {
        bridges.insert({u, v});
      }
      children++;
    }
  }
  if (lowlink[u] == tin[u]) {
    vector<int> tmp;
    int v;
    do {
      v = stack.back();
      stack.pop_back();
      tmp.push_back(v);
    } while (u != v);
    blocks.push_back(tmp);
  }
}

void tarjan(int nodes) {
  visit.assign(nodes, false);
  lowlink.assign(nodes, 0);
  tin.assign(nodes, 0);
  bridges.clear();
  stack.clear();
  blocks.clear();
  timer = 0;
  for (int i = 0; i < nodes; i++) {
    if (!visit[i]) {
      dfs(i, -1);
    }
  }
  // Get node to block mapping.
  block.assign(nodes, 0);
  nblocks = blocks.size();
  for (int i = 0; i < nblocks; i++) {
    for (int j : blocks[i]) {
      block[j] = i;
    }
  }
  // Get bridge-block forest adjacencies.
  block_adj.assign(nblocks, {});
  for (int i = 0; i < nodes; i++) {
    for (int j : adj[i]) {
      if (block[i] != block[j]) {
        block_adj[block[i]].push_back(block[j]);
      }
    }
  }
}

// Start of code to find odd cycles/distances to odd cycle blocks.

bool no_odd_cycles;
vector<int> color;
vector<bool> has_odd_cycle;
vector<int> dist_to_odd;

bool dfs_color(int u, int c = 1) {
  // Color edges in search of an odd cycle.
  color[u] = c;
  int nextc = 3 - c;
  for (int v : adj[u]) {
    if (bridges.count({u, v}) || bridges.count({v, u})) {
      continue;
    }
    if (color[v]) {
      if (color[v] != nextc) {
        return true;
      }
    } else if (dfs_color(v, nextc)) {
      return true;
    }
  }
  return false;
}

void find_odd_cycles_and_distances() {
  color.assign(N, 0);
  has_odd_cycle.assign(nblocks, false);
  dist_to_odd.assign(nblocks, INF);
  queue<int> q;
  for (int i = 0; i < nblocks; i++) {
    has_odd_cycle[i] = dfs_color(blocks[i].front());
    if (has_odd_cycle[i]) {
      dist_to_odd[i] = 0;
      q.push(i);
    }
  }
  no_odd_cycles = q.empty();
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (int u : block_adj[v]) {
      if (dist_to_odd[u] == INF) {
        dist_to_odd[u] = dist_to_odd[v] + 1;
        q.push(u);
      }
    }
  }
}

// Start of binary lifting code for path-min queries.

vector<int> depth;
vector<vector<int>> lift, liftval;

void dfs_lift(int u, int p, int d) {
  depth[u] = d;
  lift[u][0] = p;
  liftval[u][0] = dist_to_odd[u];
  for (int v : block_adj[u]) {
    if (v != p) {
      dfs_lift(v, u, d + 1);
    }
  }
}

void init_binary_lifting() {
  depth.assign(nblocks, -1);
  lift.assign(nblocks, vector<int>(lgmax, -1));
  liftval.assign(nblocks, vector<int>(lgmax));
  dfs_lift(0, -1, 0);
  for (int e = 1; e < lgmax; e++) {
    for (int u = 0; u < nblocks; u++) {
      if (lift[u][e - 1] != -1) {
        lift[u][e] = lift[lift[u][e - 1]][e - 1];
        liftval[u][e] = min(liftval[u][e - 1], liftval[lift[u][e - 1]][e - 1]);
      }
    }
  }
}

int go_up(int u, int to_depth) {
  if (depth[u] == to_depth) {
    return u;
  }
  return go_up(lift[u][__builtin_ctz(depth[u] - to_depth)], to_depth);
}

int get_lca(int u, int v, int maxlift) {
  if (depth[u] != depth[v]) {
    if (depth[u] > depth[v]) {
      return get_lca(go_up(u, depth[v]), v, lgmax - 1);
    }
    return get_lca(u, go_up(v, depth[u]), lgmax - 1);
  }
  if (u == v) {
    return u;
  }
  if (lift[u][0] == lift[v][0]) {
    return lift[u][0];
  }
  while (lift[u][maxlift] == lift[v][maxlift]) {
    --maxlift;
  }
  return get_lca(lift[u][maxlift], lift[v][maxlift], maxlift);
}

int path_min_go_up(int u, int to_depth) {
  if (depth[u] == to_depth) {
    return dist_to_odd[u];
  }
  int e = __builtin_ctz(depth[u] - to_depth);
  return min(path_min_go_up(lift[u][e], to_depth), liftval[u][e]);
}

int path_min(int u, int v) {
  int lca = get_lca(u, v, lgmax - 1);
  return min(path_min_go_up(u, depth[lca]), path_min_go_up(v, depth[lca]));
}

// Main Solution.

long long solve() {
  cin >> N >> M;
  adj.assign(N, {});
  for (int i = 0, u, v; i < M; i++) {
    cin >> u >> v;
    --u, --v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  // Find bridges and bridge block tree.
  tarjan(N);
  // Find odd cycle blocks, and min-distance to odd cycles from each block.
  find_odd_cycles_and_distances();
  // Initialize binary lifting for path mins.
  init_binary_lifting();
  // Process queries.
  long long ans = 0;
  cin >> Q;
  for (int i = 0, a, b; i < Q; i++) {
    cin >> a >> b;
    --a, --b;
    ans += no_odd_cycles ? -1 : path_min(block[a], block[b]);
  }
  return ans;
}

int main() {
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    cout << "Case #" << t << ": " << solve() << endl;
  }
  return 0;
}