// A/B — grid DFS. Sink as you go; the visited array is the grid itself.
static final int[][] DIRS = {{1,0},{-1,0},{0,1},{0,-1}};

int dfs(char[][] g, int r, int c) {
    if (r < 0 || r >= g.length || c < 0 || c >= g[0].length || g[r][c] != '1') return 0;
    g[r][c] = '0';                       // mark BEFORE recursing
    int size = 1;
    for (int[] d : DIRS) size += dfs(g, r + d[0], c + d[1]);
    return size;
}

// C — grid BFS. Distance is the level index. Mark on push.
int bfs(int[][] g, int sr, int sc, int tr, int tc) {
    int m = g.length, n = g[0].length;
    boolean[][] seen = new boolean[m][n];
    Deque<int[]> q = new ArrayDeque<>();
    q.add(new int[]{sr, sc});
    seen[sr][sc] = true;                 // on push, not on pop
    for (int dist = 0; !q.isEmpty(); dist++) {
        for (int sz = q.size(); sz > 0; sz--) {
            int[] cur = q.poll();
            if (cur[0] == tr && cur[1] == tc) return dist;
            for (int[] d : DIRS) {
                int nr = cur[0] + d[0], nc = cur[1] + d[1];
                if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
                if (seen[nr][nc] || g[nr][nc] == 1) continue;
                seen[nr][nc] = true;
                q.add(new int[]{nr, nc});
            }
        }
    }
    return -1;
}

// D — multi-source BFS. Every source is seeded before the first pop.
Deque<int[]> q = new ArrayDeque<>();
for (int r = 0; r < m; r++)
    for (int c = 0; c < n; c++)
        if (isSource(g[r][c])) { q.add(new int[]{r, c}); seen[r][c] = true; }
// ...then the identical level loop as above.

// E — adjacency list from an edge list. Undirected adds both directions.
List<Integer>[] build(int n, int[][] edges, boolean directed) {
    List<Integer>[] adj = new List[n];
    for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
    for (int[] e : edges) {
        adj[e[0]].add(e[1]);
        if (!directed) adj[e[1]].add(e[0]);
    }
    return adj;
}

// F — undirected cycle detection. Skip the parent, not the visited set.
boolean hasCycle(List<Integer>[] adj, int u, int parent, boolean[] seen) {
    seen[u] = true;
    for (int v : adj[u]) {
        if (v == parent) continue;                     // the one exception
        if (seen[v]) return true;
        if (hasCycle(adj, v, u, seen)) return true;
    }
    return false;
}
// A graph is a TREE iff edges == n - 1 AND one DFS from node 0 marks every node.

// G — bipartite check. 0 = unvisited, 1 / -1 = the two colours.
boolean isBipartite(List<Integer>[] adj, int n) {
    int[] color = new int[n];
    for (int s = 0; s < n; s++) {
        if (color[s] != 0) continue;                   // disconnected components
        Deque<Integer> q = new ArrayDeque<>(List.of(s));
        color[s] = 1;
        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : adj[u]) {
                if (color[v] == color[u]) return false;
                if (color[v] == 0) { color[v] = -color[u]; q.add(v); }
            }
        }
    }
    return true;
}

// J — state-space BFS. Only the encode/decode changes between problems.
int bfs(String start, String target, Set<String> blocked) {
    if (blocked.contains(start)) return -1;
    Set<String> seen = new HashSet<>(List.of(start));
    Deque<String> q = new ArrayDeque<>(List.of(start));
    for (int dist = 0; !q.isEmpty(); dist++) {
        for (int sz = q.size(); sz > 0; sz--) {
            String cur = q.poll();
            if (cur.equals(target)) return dist;
            for (String nxt : neighbours(cur)) {
                if (seen.contains(nxt) || blocked.contains(nxt)) continue;
                seen.add(nxt);
                q.add(nxt);
            }
        }
    }
    return -1;
}