Minimum edge reversals so every node is reachable

impl Solution {
  pub fn min_edge_reversals(n: i32, edges: Vec<Vec<i32>>) -> Vec<i32> {
    let n = n as usize;
    // Build undirected adjacency list with edge cost: 0 if following original dir, 1 if reversed
    let mut adj = vec![vec![]; n];
    for e in &edges {
      let u = e[0] as usize;
      let v = e[1] as usize;
      adj[u].push((v, 0)); // forward: cost 0
      adj[v].push((u, 1)); // backward: cost 1 (need reversal)
    }
    // BFS/DFS from node 0 to compute answer[0]
    let mut cost = vec![i32::MAX; n];
    cost[0] = 0;
    let mut queue = std::collections::VecDeque::new();
    queue.push_back(0usize);
    // Actually use 0-1 BFS
    let mut dist = vec![i32::MAX; n];
    dist[0] = 0;
    queue.clear();
    queue.push_back(0usize);
    while let Some(u) = queue.pop_front() {
      for &(v, w) in &adj[u] {
        let nd = dist[u] + w;
        if nd < dist[v] {
          dist[v] = nd;
          if w == 0 { queue.push_front(v); } else { queue.push_back(v); }
        }
      }
    }
    let _base = dist[0]; // but we want sum for node 0
    // Re-do: BFS from node 0 accumulating sum of reversals to reach all nodes
    // Actually dist[v] = min reversals from 0 to v for any single v, but answer[0] = sum? No.
    // answer[i] = min reversals to reach ALL nodes from i
    // Re-interpret: for each node, we need to reach every other node. This is a tree rerooting problem.
    // Step 1: Root tree at 0, compute reversals needed from 0 (= number of backward edges on tree)
    // Step 2: Re-root DP: when we move root from u to neighbor v:
    //   if edge u->v (original forward), cost increases by 1 (now need to reverse it)
    //   if edge v->u (original backward from u's perspective, cost 1), cost decreases by 1
    let mut ans = vec![0i32; n];
    // DFS from node 0: count how many edges need reversal rooting at 0
    let mut visited = vec![false; n];
    visited[0] = true;
    let _stack = vec![(0usize, 0i32)];
    let mut order = vec![];
    let mut parent = vec![0usize; n];
    let mut parent_cost = vec![0i32; n];
    // iterative DFS
    let mut s = vec![(0usize, usize::MAX, 0i32)]; // (node, parent, cost_from_parent)
    while let Some((u, p, c)) = s.pop() {
      order.push(u);
      if p != usize::MAX { parent[u] = p; parent_cost[u] = c; }
      for &(v, w) in &adj[u] {
        if v != p {
          s.push((v, u, w));
        }
      }
    }
    // Compute ans[0] = sum of reversed edges (cost=1 from adj perspective when going forward)
    // From 0 outward: edge cost w=0 means original direction matches (no reversal), w=1 means reversal needed
    // Wait: adj[u].push((v, 0)) means u->v original forward, reaching v from u costs 0
    //       adj[v].push((u, 1)) means going from v to u (backward original) costs 1 reversal
    // So from node 0, ans[0] = sum of w on the DFS tree edges
    let mut ans0 = 0i32;
    for i in 1..n { ans0 += parent_cost[i]; }
    ans[0] = ans0;
    // Re-root: process nodes in BFS order from 0
    let mut bfs_order = vec![];
    let mut par = vec![usize::MAX; n];
    let mut par_w = vec![0i32; n]; // weight of edge from parent to this node (0 or 1)
    let mut vis2 = vec![false; n];
    vis2[0] = true;
    let mut q = std::collections::VecDeque::new();
    q.push_back(0usize);
    while let Some(u) = q.pop_front() {
      bfs_order.push(u);
      for &(v, w) in &adj[u] {
        if !vis2[v] {
          vis2[v] = true;
          par[v] = u;
          par_w[v] = w; // cost of going u->v in tree
          q.push_back(v);
        }
      }
    }
    for &u in bfs_order.iter().skip(1) {
      let p = par[u];
      let w = par_w[u]; // cost from p to u
      // Moving root from p to u:
      // if w=0 (p->u original forward): from u's perspective need to go back to p, costs 1 reversal more
      // if w=1 (u->p original forward, reversed to reach u from p): from u's perspective follow original = saves 1 reversal
      if w == 0 {
        ans[u] = ans[p] + 1;
      } else {
        ans[u] = ans[p] - 1;
      }
    }
    ans
  }
}