Graphs.
Scratch se advanced tak.

int[][] adj = new int[n][n];
for (int[] e : edges) {
    adj[e[0]][e[1]] = 1;
    adj[e[1]][e[0]] = 1;   // ye line sirf undirected me
}

List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());

for (int[] e : edges) {
    adj.get(e[0]).add(e[1]);
    adj.get(e[1]).add(e[0]);   // undirected hi me
}

List<int[]>[] adj = new List[n];
for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();

for (int[] e : edges) {           // e = {u, v, wt}
    adj[e[0]].add(new int[]{e[1], e[2]});
    adj[e[1]].add(new int[]{e[0], e[2]});
}
// use: for (int[] nb : adj[u]) { int v = nb[0], wt = nb[1]; ... }

void bfs(int src, List<List<Integer>> adj, boolean[] vis) {
    Queue<Integer> q = new LinkedList<>();
    q.add(src);
    vis[src] = true;               // MARK KARO PUSH KE WAQT

    while (!q.isEmpty()) {
        int node = q.poll();
        System.out.print(node + " ");

        for (int nb : adj.get(node)) {
            if (!vis[nb]) {
                vis[nb] = true;
                q.add(nb);
            }
        }
    }
}

int level = 0;
while (!q.isEmpty()) {
    int sz = q.size();             // is level me kitne hain, snapshot
    for (int i = 0; i < sz; i++) {
        int node = q.poll();
        for (int nb : adj.get(node)) {
            if (!vis[nb]) { vis[nb] = true; q.add(nb); }
        }
    }
    level++;                       // ek poori layer khatam
}

void dfs(int node, List<List<Integer>> adj, boolean[] vis) {
    vis[node] = true;
    System.out.print(node + " ");

    for (int nb : adj.get(node)) {
        if (!vis[nb]) dfs(nb, adj, vis);
    }
}

Deque<Integer> st = new ArrayDeque<>();
st.push(src);
while (!st.isEmpty()) {
    int node = st.pop();
    if (vis[node]) continue;       // yahan check, kyunki duplicate push ho sakte hain
    vis[node] = true;
    System.out.print(node + " ");
    for (int nb : adj.get(node)) if (!vis[nb]) st.push(nb);
}

public int findCircleNum(int[][] isConnected) {
    int n = isConnected.length;
    boolean[] vis = new boolean[n];
    int count = 0;

    for (int i = 0; i < n; i++) {
        if (!vis[i]) {          // naya component mila
            count++;
            dfs(i, isConnected, vis);
        }
    }
    return count;
}

private void dfs(int u, int[][] g, boolean[] vis) {
    vis[u] = true;
    for (int v = 0; v < g.length; v++) {
        if (g[u][v] == 1 && !vis[v]) dfs(v, g, vis);
    }
}

public int numIslands(char[][] grid) {
    int n = grid.length, m = grid[0].length, count = 0;
    boolean[][] vis = new boolean[n][m];

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!vis[i][j] && grid[i][j] == '1') {
                count++;
                bfs(i, j, grid, vis);
            }
        }
    }
    return count;
}

private void bfs(int r, int c, char[][] grid, boolean[][] vis) {
    int n = grid.length, m = grid[0].length;
    int[] dr = {-1, 0, 1, 0}, dc = {0, 1, 0, -1};
    Queue<int[]> q = new LinkedList<>();
    q.add(new int[]{r, c});
    vis[r][c] = true;

    while (!q.isEmpty()) {
        int[] cell = q.poll();
        for (int k = 0; k < 4; k++) {
            int nr = cell[0] + dr[k], nc = cell[1] + dc[k];
            if (nr >= 0 && nr < n && nc >= 0 && nc < m
                    && !vis[nr][nc] && grid[nr][nc] == '1') {
                vis[nr][nc] = true;
                q.add(new int[]{nr, nc});
            }
        }
    }
}

public int[][] floodFill(int[][] image, int sr, int sc, int color) {
    int old = image[sr][sc];
    if (old == color) return image;      // *** ye line na ho toh infinite loop ***
    dfs(image, sr, sc, old, color);
    return image;
}

private void dfs(int[][] img, int r, int c, int old, int nw) {
    if (r < 0 || r >= img.length || c < 0 || c >= img[0].length) return;
    if (img[r][c] != old) return;

    img[r][c] = nw;                      // yahi "visited" ka kaam bhi kar raha hai
    dfs(img, r - 1, c, old, nw);
    dfs(img, r + 1, c, old, nw);
    dfs(img, r, c - 1, old, nw);
    dfs(img, r, c + 1, old, nw);
}

public int orangesRotting(int[][] grid) {
    int n = grid.length, m = grid[0].length;
    Queue<int[]> q = new LinkedList<>();
    int fresh = 0;

    // STEP 1: saare sources queue me, aur fresh gino
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 2) q.add(new int[]{i, j});
            else if (grid[i][j] == 1) fresh++;
        }

    if (fresh == 0) return 0;          // *** edge case: koi fresh hi nahi ***

    int time = 0;
    int[] dr = {-1, 0, 1, 0}, dc = {0, 1, 0, -1};

    // STEP 2: level-wise BFS
    while (!q.isEmpty()) {
        int sz = q.size();
        boolean sadaAny = false;

        for (int i = 0; i < sz; i++) {
            int[] cur = q.poll();
            for (int k = 0; k < 4; k++) {
                int nr = cur[0] + dr[k], nc = cur[1] + dc[k];
                if (nr >= 0 && nr < n && nc >= 0 && nc < m && grid[nr][nc] == 1) {
                    grid[nr][nc] = 2;      // rotten = visited
                    fresh--;
                    sadaAny = true;
                    q.add(new int[]{nr, nc});
                }
            }
        }
        if (sadaAny) time++;           // is second me kuch sada tabhi ginte hain
    }

    return fresh == 0 ? time : -1;
}

public int[][] updateMatrix(int[][] mat) {
    int n = mat.length, m = mat[0].length;
    int[][] dist = new int[n][m];
    boolean[][] vis = new boolean[n][m];
    Queue<int[]> q = new LinkedList<>();

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (mat[i][j] == 0) { q.add(new int[]{i, j, 0}); vis[i][j] = true; }

    int[] dr = {-1, 0, 1, 0}, dc = {0, 1, 0, -1};

    while (!q.isEmpty()) {
        int[] cur = q.poll();
        int r = cur[0], c = cur[1], d = cur[2];
        dist[r][c] = d;

        for (int k = 0; k < 4; k++) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr >= 0 && nr < n && nc >= 0 && nc < m && !vis[nr][nc]) {
                vis[nr][nc] = true;
                q.add(new int[]{nr, nc, d + 1});
            }
        }
    }
    return dist;
}

public void solve(char[][] board) {
    int n = board.length, m = board[0].length;
    boolean[][] safe = new boolean[n][m];

    // pehli aur aakhri column
    for (int i = 0; i < n; i++) {
        if (board[i][0] == 'O' && !safe[i][0])       dfs(i, 0, board, safe);
        if (board[i][m-1] == 'O' && !safe[i][m-1])   dfs(i, m-1, board, safe);
    }
    // pehli aur aakhri row
    for (int j = 0; j < m; j++) {
        if (board[0][j] == 'O' && !safe[0][j])       dfs(0, j, board, safe);
        if (board[n-1][j] == 'O' && !safe[n-1][j])   dfs(n-1, j, board, safe);
    }

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (board[i][j] == 'O' && !safe[i][j]) board[i][j] = 'X';
}

private void dfs(int r, int c, char[][] b, boolean[][] safe) {
    int n = b.length, m = b[0].length;
    safe[r][c] = true;
    int[] dr = {-1, 0, 1, 0}, dc = {0, 1, 0, -1};
    for (int k = 0; k < 4; k++) {
        int nr = r + dr[k], nc = c + dc[k];
        if (nr >= 0 && nr < n && nc >= 0 && nc < m
                && !safe[nr][nc] && b[nr][nc] == 'O') {
            dfs(nr, nc, b, safe);
        }
    }
}

public int numEnclaves(int[][] grid) {
    int n = grid.length, m = grid[0].length;
    boolean[][] vis = new boolean[n][m];
    Queue<int[]> q = new LinkedList<>();

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if ((i == 0 || j == 0 || i == n-1 || j == m-1) && grid[i][j] == 1) {
                q.add(new int[]{i, j});
                vis[i][j] = true;
            }

    int[] dr = {-1, 0, 1, 0}, dc = {0, 1, 0, -1};
    while (!q.isEmpty()) {
        int[] cur = q.poll();
        for (int k = 0; k < 4; k++) {
            int nr = cur[0] + dr[k], nc = cur[1] + dc[k];
            if (nr >= 0 && nr < n && nc >= 0 && nc < m
                    && !vis[nr][nc] && grid[nr][nc] == 1) {
                vis[nr][nc] = true;
                q.add(new int[]{nr, nc});
            }
        }
    }

    int count = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (grid[i][j] == 1 && !vis[i][j]) count++;
    return count;
}

public int countDistinctIslands(int[][] grid) {
    int n = grid.length, m = grid[0].length;
    boolean[][] vis = new boolean[n][m];
    Set<String> shapes = new HashSet<>();

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (!vis[i][j] && grid[i][j] == 1) {
                StringBuilder sb = new StringBuilder();
                dfs(i, j, i, j, grid, vis, sb);   // base = (i, j)
                shapes.add(sb.toString());
            }
    return shapes.size();
}

private void dfs(int r, int c, int r0, int c0, int[][] g,
                 boolean[][] vis, StringBuilder sb) {
    vis[r][c] = true;
    sb.append(r - r0).append(',').append(c - c0).append(' ');   // relative

    int[] dr = {-1, 0, 1, 0}, dc = {0, 1, 0, -1};
    for (int k = 0; k < 4; k++) {
        int nr = r + dr[k], nc = c + dc[k];
        if (nr >= 0 && nr < g.length && nc >= 0 && nc < g[0].length
                && !vis[nr][nc] && g[nr][nc] == 1) {
            dfs(nr, nc, r0, c0, g, vis, sb);
        }
    }
}

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    Set<String> set = new HashSet<>(wordList);
    if (!set.contains(endWord)) return 0;      // *** edge case ***

    Queue<String> q = new LinkedList<>();
    q.add(beginWord);
    set.remove(beginWord);                      // visited ka kaam set hi kar raha hai
    int steps = 1;

    while (!q.isEmpty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            String word = q.poll();
            if (word.equals(endWord)) return steps;

            char[] arr = word.toCharArray();
            for (int pos = 0; pos < arr.length; pos++) {
                char original = arr[pos];
                for (char ch = 'a'; ch <= 'z'; ch++) {
                    if (ch == original) continue;
                    arr[pos] = ch;
                    String next = new String(arr);
                    if (set.contains(next)) {
                        set.remove(next);       // dobara visit na ho
                        q.add(next);
                    }
                }
                arr[pos] = original;            // *** restore karo ***
            }
        }
        steps++;
    }
    return 0;
}

public boolean isCycle(int V, List<List<Integer>> adj) {
    boolean[] vis = new boolean[V];
    for (int i = 0; i < V; i++)             // disconnected components!
        if (!vis[i] && bfsCheck(i, adj, vis)) return true;
    return false;
}

private boolean bfsCheck(int src, List<List<Integer>> adj, boolean[] vis) {
    Queue<int[]> q = new LinkedList<>();   // {node, parent}
    q.add(new int[]{src, -1});
    vis[src] = true;

    while (!q.isEmpty()) {
        int[] cur = q.poll();
        int node = cur[0], parent = cur[1];

        for (int nb : adj.get(node)) {
            if (!vis[nb]) {
                vis[nb] = true;
                q.add(new int[]{nb, node});
            } else if (nb != parent) {
                return true;                // visited + parent nahi = cycle
            }
        }
    }
    return false;
}

public boolean isCycle(int V, List<List<Integer>> adj) {
    boolean[] vis = new boolean[V];
    for (int i = 0; i < V; i++)
        if (!vis[i] && dfs(i, -1, adj, vis)) return true;
    return false;
}

private boolean dfs(int node, int parent, List<List<Integer>> adj, boolean[] vis) {
    vis[node] = true;
    for (int nb : adj.get(node)) {
        if (!vis[nb]) {
            if (dfs(nb, node, adj, vis)) return true;   // *** return propagate karo ***
        } else if (nb != parent) {
            return true;
        }
    }
    return false;
}

public boolean isBipartite(int[][] graph) {
    int n = graph.length;
    int[] color = new int[n];
    Arrays.fill(color, -1);                 // -1 = abhi rangaa nahi

    for (int i = 0; i < n; i++) {
        if (color[i] != -1) continue;

        Queue<Integer> q = new LinkedList<>();
        q.add(i);
        color[i] = 0;

        while (!q.isEmpty()) {
            int node = q.poll();
            for (int nb : graph[node]) {
                if (color[nb] == -1) {
                    color[nb] = 1 - color[node];    // ulta colour
                    q.add(nb);
                } else if (color[nb] == color[node]) {
                    return false;                   // conflict
                }
            }
        }
    }
    return true;
}

private boolean dfs(int node, int col, int[][] g, int[] color) {
    color[node] = col;
    for (int nb : g[node]) {
        if (color[nb] == -1) {
            if (!dfs(nb, 1 - col, g, color)) return false;
        } else if (color[nb] == col) return false;
    }
    return true;
}

public boolean isCyclic(int V, List<List<Integer>> adj) {
    boolean[] vis = new boolean[V], pathVis = new boolean[V];
    for (int i = 0; i < V; i++)
        if (!vis[i] && dfs(i, adj, vis, pathVis)) return true;
    return false;
}

private boolean dfs(int node, List<List<Integer>> adj,
                    boolean[] vis, boolean[] pathVis) {
    vis[node] = true;
    pathVis[node] = true;

    for (int nb : adj.get(node)) {
        if (!vis[nb]) {
            if (dfs(nb, adj, vis, pathVis)) return true;
        } else if (pathVis[nb]) {
            return true;                  // back edge = cycle
        }
    }

    pathVis[node] = false;                // *** BACKTRACK — ye line hi sab kuch hai ***
    return false;
}

public List<Integer> eventualSafeNodes(int[][] graph) {
    int n = graph.length;
    boolean[] vis = new boolean[n], pathVis = new boolean[n], safe = new boolean[n];

    for (int i = 0; i < n; i++)
        if (!vis[i]) dfs(i, graph, vis, pathVis, safe);

    List<Integer> res = new ArrayList<>();
    for (int i = 0; i < n; i++) if (safe[i]) res.add(i);
    return res;                          // 0..n-1 loop se already sorted
}

private boolean dfs(int node, int[][] g, boolean[] vis,
                    boolean[] pathVis, boolean[] safe) {
    vis[node] = true;
    pathVis[node] = true;

    for (int nb : g[node]) {
        if (!vis[nb]) {
            if (dfs(nb, g, vis, pathVis, safe)) return true;   // cycle mila
        } else if (pathVis[nb]) return true;
    }

    pathVis[node] = false;
    safe[node] = true;                   // yahan tak pahunche = koi cycle nahi mila
    return false;
}

public int[] topoSort(int V, List<List<Integer>> adj) {
    boolean[] vis = new boolean[V];
    Deque<Integer> st = new ArrayDeque<>();

    for (int i = 0; i < V; i++) if (!vis[i]) dfs(i, adj, vis, st);

    int[] res = new int[V];
    int idx = 0;
    while (!st.isEmpty()) res[idx++] = st.pop();   // ulta padho
    return res;
}

private void dfs(int node, List<List<Integer>> adj, boolean[] vis, Deque<Integer> st) {
    vis[node] = true;
    for (int nb : adj.get(node)) if (!vis[nb]) dfs(nb, adj, vis, st);
    st.push(node);              // *** RETURN ke waqt push — entry pe nahi ***
}

public int[] topoSort(int V, List<List<Integer>> adj) {
    int[] indeg = new int[V];
    for (int u = 0; u < V; u++)
        for (int v : adj.get(u)) indeg[v]++;

    Queue<Integer> q = new LinkedList<>();
    for (int i = 0; i < V; i++) if (indeg[i] == 0) q.add(i);

    int[] res = new int[V];
    int idx = 0;
    while (!q.isEmpty()) {
        int node = q.poll();
        res[idx++] = node;
        for (int nb : adj.get(node)) {
            if (--indeg[nb] == 0) q.add(nb);
        }
    }
    return res;      // agar idx < V hai toh cycle thi (Q21 dekho)
}

public boolean isCyclic(int V, List<List<Integer>> adj) {
    int[] indeg = new int[V];
    for (int u = 0; u < V; u++) for (int v : adj.get(u)) indeg[v]++;

    Queue<Integer> q = new LinkedList<>();
    for (int i = 0; i < V; i++) if (indeg[i] == 0) q.add(i);

    int count = 0;
    while (!q.isEmpty()) {
        int node = q.poll();
        count++;
        for (int nb : adj.get(node)) if (--indeg[nb] == 0) q.add(nb);
    }
    return count != V;          // sab nahi nikle = cycle hai
}

public int[] findOrder(int numCourses, int[][] prerequisites) {
    int n = numCourses;
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());

    int[] indeg = new int[n];
    for (int[] p : prerequisites) {
        adj.get(p[1]).add(p[0]);      // p[1] pehle → p[0]
        indeg[p[0]]++;
    }

    Queue<Integer> q = new LinkedList<>();
    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.add(i);

    int[] res = new int[n];
    int idx = 0;
    while (!q.isEmpty()) {
        int node = q.poll();
        res[idx++] = node;
        for (int nb : adj.get(node)) if (--indeg[nb] == 0) q.add(nb);
    }

    return idx == n ? res : new int[0];   // cycle → empty
}

// Course Schedule I: bas   return idx == n;

public String findOrder(String[] dict, int N, int K) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < K; i++) adj.add(new ArrayList<>());
    int[] indeg = new int[K];

    for (int i = 0; i < N - 1; i++) {
        String s1 = dict[i], s2 = dict[i + 1];
        int len = Math.min(s1.length(), s2.length());
        for (int j = 0; j < len; j++) {
            if (s1.charAt(j) != s2.charAt(j)) {
                int u = s1.charAt(j) - 'a', v = s2.charAt(j) - 'a';
                adj.get(u).add(v);
                indeg[v]++;
                break;                    // *** pehla farak hi rule deta hai ***
            }
        }
    }

    Queue<Integer> q = new LinkedList<>();
    for (int i = 0; i < K; i++) if (indeg[i] == 0) q.add(i);

    StringBuilder sb = new StringBuilder();
    while (!q.isEmpty()) {
        int node = q.poll();
        sb.append((char)(node + 'a'));
        for (int nb : adj.get(node)) if (--indeg[nb] == 0) q.add(nb);
    }
    return sb.length() == K ? sb.toString() : "";
}

public int[] shortestPath(int V, int E, int[][] edges) {
    List<int[]>[] adj = new List[V];
    for (int i = 0; i < V; i++) adj[i] = new ArrayList<>();
    for (int[] e : edges) adj[e[0]].add(new int[]{e[1], e[2]});   // u, v, wt

    // 1) topo order
    boolean[] vis = new boolean[V];
    Deque<Integer> st = new ArrayDeque<>();
    for (int i = 0; i < V; i++) if (!vis[i]) topo(i, adj, vis, st);

    // 2) relax in topo order
    int[] dist = new int[V];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[0] = 0;

    while (!st.isEmpty()) {
        int u = st.pop();
        if (dist[u] == Integer.MAX_VALUE) continue;   // u tak pahunche hi nahi

        for (int[] nb : adj[u]) {
            int v = nb[0], wt = nb[1];
            if (dist[u] + wt < dist[v]) dist[v] = dist[u] + wt;
        }
    }

    for (int i = 0; i < V; i++) if (dist[i] == Integer.MAX_VALUE) dist[i] = -1;
    return dist;
}

private void topo(int u, List<int[]>[] adj, boolean[] vis, Deque<Integer> st) {
    vis[u] = true;
    for (int[] nb : adj[u]) if (!vis[nb[0]]) topo(nb[0], adj, vis, st);
    st.push(u);
}

public int[] shortestPath(List<List<Integer>> adj, int V, int src) {
    int[] dist = new int[V];
    Arrays.fill(dist, -1);
    dist[src] = 0;

    Queue<Integer> q = new LinkedList<>();
    q.add(src);

    while (!q.isEmpty()) {
        int node = q.poll();
        for (int nb : adj.get(node)) {
            if (dist[nb] == -1) {                 // pehli baar pahunche = shortest
                dist[nb] = dist[node] + 1;
                q.add(nb);
            }
        }
    }
    return dist;
}

public int[] dijkstra(int V, List<int[]>[] adj, int src) {
    int[] dist = new int[V];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;

    // {distance, node} — distance pe sort
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    pq.add(new int[]{0, src});

    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int d = cur[0], u = cur[1];

        if (d > dist[u]) continue;          // *** stale entry — skip ***

        for (int[] nb : adj[u]) {
            int v = nb[0], wt = nb[1];
            if (d + wt < dist[v]) {
                dist[v] = d + wt;
                pq.add(new int[]{dist[v], v});
            }
        }
    }
    return dist;
}

public List<Integer> shortestPath(int n, int m, int[][] edges) {
    List<int[]>[] adj = new List[n + 1];
    for (int i = 1; i <= n; i++) adj[i] = new ArrayList<>();
    for (int[] e : edges) {
        adj[e[0]].add(new int[]{e[1], e[2]});
        adj[e[1]].add(new int[]{e[0], e[2]});
    }

    int[] dist = new int[n + 1], parent = new int[n + 1];
    Arrays.fill(dist, Integer.MAX_VALUE);
    for (int i = 1; i <= n; i++) parent[i] = i;     // apna hi parent = shuruaat
    dist[1] = 0;

    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    pq.add(new int[]{0, 1});

    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int d = cur[0], u = cur[1];
        if (d > dist[u]) continue;
        for (int[] nb : adj[u]) {
            int v = nb[0], wt = nb[1];
            if (d + wt < dist[v]) {
                dist[v] = d + wt;
                parent[v] = u;                     // *** yahan yaad rakho ***
                pq.add(new int[]{dist[v], v});
            }
        }
    }

    List<Integer> path = new ArrayList<>();
    if (dist[n] == Integer.MAX_VALUE) { path.add(-1); return path; }

    int node = n;
    while (parent[node] != node) {                 // source pe parent khud hota hai
        path.add(node);
        node = parent[node];
    }
    path.add(1);
    Collections.reverse(path);
    return path;
}

public int shortestPath(int[][] grid, int[] src, int[] dest) {
    if (src[0] == dest[0] && src[1] == dest[1]) return 0;
    int n = grid.length, m = grid[0].length;

    int[][] dist = new int[n][m];
    for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
    dist[src[0]][src[1]] = 0;

    Queue<int[]> q = new LinkedList<>();
    q.add(new int[]{src[0], src[1]});
    int[] dr = {-1, 0, 1, 0}, dc = {0, 1, 0, -1};

    while (!q.isEmpty()) {
        int[] cur = q.poll();
        int r = cur[0], c = cur[1];
        for (int k = 0; k < 4; k++) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr >= 0 && nr < n && nc >= 0 && nc < m
                    && grid[nr][nc] == 1 && dist[r][c] + 1 < dist[nr][nc]) {
                dist[nr][nc] = dist[r][c] + 1;
                if (nr == dest[0] && nc == dest[1]) return dist[nr][nc];  // early exit
                q.add(new int[]{nr, nc});
            }
        }
    }
    return -1;
}

public int minimumEffortPath(int[][] heights) {
    int n = heights.length, m = heights[0].length;
    int[][] eff = new int[n][m];
    for (int[] row : eff) Arrays.fill(row, Integer.MAX_VALUE);
    eff[0][0] = 0;

    // {effort, row, col}
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    pq.add(new int[]{0, 0, 0});
    int[] dr = {-1, 0, 1, 0}, dc = {0, 1, 0, -1};

    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int d = cur[0], r = cur[1], c = cur[2];

        if (r == n - 1 && c == m - 1) return d;    // pop = final, return kar do
        if (d > eff[r][c]) continue;

        for (int k = 0; k < 4; k++) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;

            int newEff = Math.max(d, Math.abs(heights[nr][nc] - heights[r][c]));
            if (newEff < eff[nr][nc]) {
                eff[nr][nc] = newEff;
                pq.add(new int[]{newEff, nr, nc});
            }
        }
    }
    return 0;
}

public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
    List<int[]>[] adj = new List[n];
    for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
    for (int[] f : flights) adj[f[0]].add(new int[]{f[1], f[2]});

    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;

    Queue<int[]> q = new LinkedList<>();   // {node, cost}
    q.add(new int[]{src, 0});
    int stops = 0;

    while (!q.isEmpty() && stops <= k) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            int[] cur = q.poll();
            int u = cur[0], cost = cur[1];
            for (int[] nb : adj[u]) {
                int v = nb[0], w = nb[1];
                if (cost + w < dist[v]) {
                    dist[v] = cost + w;
                    q.add(new int[]{v, cost + w});
                }
            }
        }
        stops++;
    }
    return dist[dst] == Integer.MAX_VALUE ? -1 : dist[dst];
}

public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;

    for (int round = 0; round <= k; round++) {     // k+1 edges tak
        int[] temp = dist.clone();                 // *** clone zaroori hai ***
        for (int[] f : flights) {
            int u = f[0], v = f[1], w = f[2];
            if (dist[u] != Integer.MAX_VALUE && dist[u] + w < temp[v]) {
                temp[v] = dist[u] + w;
            }
        }
        dist = temp;
    }
    return dist[dst] == Integer.MAX_VALUE ? -1 : dist[dst];
}

public int countPaths(int n, int[][] roads) {
    final int MOD = 1_000_000_007;
    List<long[]>[] adj = new List[n];
    for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
    for (int[] r : roads) {
        adj[r[0]].add(new long[]{r[1], r[2]});
        adj[r[1]].add(new long[]{r[0], r[2]});
    }

    long[] dist = new long[n];
    long[] ways = new long[n];
    Arrays.fill(dist, Long.MAX_VALUE);
    dist[0] = 0;
    ways[0] = 1;

    PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
    pq.add(new long[]{0, 0});

    while (!pq.isEmpty()) {
        long[] cur = pq.poll();
        long d = cur[0];
        int u = (int) cur[1];
        if (d > dist[u]) continue;

        for (long[] nb : adj[u]) {
            int v = (int) nb[0];
            long w = nb[1];

            if (d + w < dist[v]) {
                dist[v] = d + w;
                ways[v] = ways[u];                       // reset
                pq.add(new long[]{dist[v], v});
            } else if (d + w == dist[v]) {
                ways[v] = (ways[v] + ways[u]) % MOD;     // add
            }
        }
    }
    return (int) (ways[n - 1] % MOD);
}

public int[] bellmanFord(int V, int[][] edges, int src) {
    int[] dist = new int[V];
    Arrays.fill(dist, (int) 1e8);          // MAX_VALUE ki jagah bada sentinel
    dist[src] = 0;

    // V-1 rounds
    for (int i = 0; i < V - 1; i++) {
        for (int[] e : edges) {
            int u = e[0], v = e[1], w = e[2];
            if (dist[u] != (int) 1e8 && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
        }
    }

    // Vth round: agar ab bhi kam ho raha hai → negative cycle
    for (int[] e : edges) {
        int u = e[0], v = e[1], w = e[2];
        if (dist[u] != (int) 1e8 && dist[u] + w < dist[v]) {
            return new int[]{-1};          // negative cycle
        }
    }
    return dist;
}

public void shortestDistance(int[][] dist) {
    int n = dist.length;

    // -1 (no edge) ko bada sentinel banao
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            if (dist[i][j] == -1) dist[i][j] = (int) 1e9;
            if (i == j) dist[i][j] = 0;
        }

    for (int k = 0; k < n; k++)             // *** k sabse bahar ***
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];

    // negative cycle: dist[i][i] < 0
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (dist[i][j] == (int) 1e9) dist[i][j] = -1;
}

public int findTheCity(int n, int[][] edges, int distanceThreshold) {
    int[][] dist = new int[n][n];
    for (int[] row : dist) Arrays.fill(row, (int) 1e9);
    for (int i = 0; i < n; i++) dist[i][i] = 0;

    for (int[] e : edges) {
        dist[e[0]][e[1]] = e[2];
        dist[e[1]][e[0]] = e[2];          // undirected
    }

    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];

    int best = n + 1, ans = -1;
    for (int i = 0; i < n; i++) {
        int cnt = 0;
        for (int j = 0; j < n; j++)
            if (i != j && dist[i][j] <= distanceThreshold) cnt++;

        if (cnt <= best) {                // <= isliye ki tie pe bada index jeete
            best = cnt;
            ans = i;
        }
    }
    return ans;
}

class DSU {
    int[] parent, size;
    int components;

    DSU(int n) {
        parent = new int[n];
        size = new int[n];
        components = n;
        for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
    }

    int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);      // *** path compression ***
    }

    boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;              // already same group

        if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
        parent[rb] = ra;                          // chhota bade ke neeche
        size[ra] += size[rb];
        components--;
        return true;
    }

    boolean connected(int a, int b) { return find(a) == find(b); }
}

public int spanningTree(int V, int[][] edges) {   // edges: {u, v, wt}
    Arrays.sort(edges, (a, b) -> a[2] - b[2]);

    DSU dsu = new DSU(V);
    int total = 0, taken = 0;

    for (int[] e : edges) {
        if (dsu.union(e[0], e[1])) {              // true = cycle nahi bani
            total += e[2];
            taken++;
            if (taken == V - 1) break;            // MST poora
        }
    }
    return total;
}

public int spanningTree(int V, List<int[]>[] adj) {
    boolean[] inMST = new boolean[V];
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);  // {wt, node}
    pq.add(new int[]{0, 0});

    int total = 0;
    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int wt = cur[0], u = cur[1];

        if (inMST[u]) continue;         // *** pop ke waqt check, push pe nahi ***
        inMST[u] = true;
        total += wt;

        for (int[] nb : adj[u]) {
            if (!inMST[nb[0]]) pq.add(new int[]{nb[1], nb[0]});
        }
    }
    return total;
}

public int makeConnected(int n, int[][] connections) {
    if (connections.length < n - 1) return -1;   // cables hi kam hain

    DSU dsu = new DSU(n);
    for (int[] c : connections) dsu.union(c[0], c[1]);

    return dsu.components - 1;
}

public List<List<String>> accountsMerge(List<List<String>> accounts) {
    int n = accounts.size();
    DSU dsu = new DSU(n);
    Map<String, Integer> emailToIdx = new HashMap<>();

    // STEP 1: same email = same insaan → union
    for (int i = 0; i < n; i++) {
        for (int j = 1; j < accounts.get(i).size(); j++) {   // j=0 naam hai
            String email = accounts.get(i).get(j);
            if (emailToIdx.containsKey(email)) {
                dsu.union(i, emailToIdx.get(email));
            } else {
                emailToIdx.put(email, i);
            }
        }
    }

    // STEP 2: har root ke neeche emails collect karo
    Map<Integer, List<String>> groups = new HashMap<>();
    for (Map.Entry<String, Integer> en : emailToIdx.entrySet()) {
        int root = dsu.find(en.getValue());
        groups.computeIfAbsent(root, x -> new ArrayList<>()).add(en.getKey());
    }

    // STEP 3: sort + naam lagao
    List<List<String>> res = new ArrayList<>();
    for (Map.Entry<Integer, List<String>> en : groups.entrySet()) {
        List<String> emails = en.getValue();
        Collections.sort(emails);
        List<String> row = new ArrayList<>();
        row.add(accounts.get(en.getKey()).get(0));    // naam
        row.addAll(emails);
        res.add(row);
    }
    return res;
}

public List<Integer> numIslands2(int n, int m, int[][] operators) {
    DSU dsu = new DSU(n * m);
    boolean[][] land = new boolean[n][m];
    List<Integer> res = new ArrayList<>();
    int count = 0;
    int[] dr = {-1, 0, 1, 0}, dc = {0, 1, 0, -1};

    for (int[] op : operators) {
        int r = op[0], c = op[1];
        if (land[r][c]) { res.add(count); continue; }   // duplicate op

        land[r][c] = true;
        count++;

        for (int k = 0; k < 4; k++) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr >= 0 && nr < n && nc >= 0 && nc < m && land[nr][nc]) {
                if (dsu.union(r * m + c, nr * m + nc)) count--;
            }
        }
        res.add(count);
    }
    return res;
}

public int largestIsland(int[][] grid) {
    int n = grid.length;
    DSU dsu = new DSU(n * n);
    int[] dr = {-1, 0, 1, 0}, dc = {0, 1, 0, -1};

    // PASS 1: existing islands jodo
    for (int r = 0; r < n; r++)
        for (int c = 0; c < n; c++) {
            if (grid[r][c] == 0) continue;
            for (int k = 0; k < 4; k++) {
                int nr = r + dr[k], nc = c + dc[k];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] == 1)
                    dsu.union(r * n + c, nr * n + nc);
            }
        }

    // PASS 2: har 0 ko flip karke dekho
    int best = 0;
    for (int r = 0; r < n; r++)
        for (int c = 0; c < n; c++) {
            if (grid[r][c] == 1) continue;

            Set<Integer> roots = new HashSet<>();
            for (int k = 0; k < 4; k++) {
                int nr = r + dr[k], nc = c + dc[k];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] == 1)
                    roots.add(dsu.find(nr * n + nc));    // *** distinct roots ***
            }

            int total = 1;
            for (int root : roots) total += dsu.size[root];
            best = Math.max(best, total);
        }

    // edge case: poora grid already 1 hai, koi 0 mila hi nahi
    for (int i = 0; i < n * n; i++) best = Math.max(best, dsu.size[dsu.find(i)]);
    return best;
}

public int removeStones(int[][] stones) {
    DSU dsu = new DSU(20002);           // rows 0..10000, cols 10001..20001
    Set<Integer> used = new HashSet<>();

    for (int[] s : stones) {
        int rowNode = s[0];
        int colNode = s[1] + 10001;
        dsu.union(rowNode, colNode);
        used.add(rowNode);
        used.add(colNode);
    }

    Set<Integer> roots = new HashSet<>();
    for (int node : used) roots.add(dsu.find(node));

    return stones.length - roots.size();
}

public int swimInWater(int[][] grid) {
    int n = grid.length;
    int[][] best = new int[n][n];
    for (int[] row : best) Arrays.fill(row, Integer.MAX_VALUE);
    best[0][0] = grid[0][0];

    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    pq.add(new int[]{grid[0][0], 0, 0});
    int[] dr = {-1, 0, 1, 0}, dc = {0, 1, 0, -1};

    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int t = cur[0], r = cur[1], c = cur[2];
        if (r == n - 1 && c == n - 1) return t;
        if (t > best[r][c]) continue;

        for (int k = 0; k < 4; k++) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
            int nt = Math.max(t, grid[nr][nc]);       // *** max, sum nahi ***
            if (nt < best[nr][nc]) {
                best[nr][nc] = nt;
                pq.add(new int[]{nt, nr, nc});
            }
        }
    }
    return -1;
}

public int swimInWater(int[][] grid) {
    int n = grid.length;
    int[] pos = new int[n * n];              // elevation -> cell index
    for (int r = 0; r < n; r++)
        for (int c = 0; c < n; c++) pos[grid[r][c]] = r * n + c;

    DSU dsu = new DSU(n * n);
    boolean[] open = new boolean[n * n];
    int[] dr = {-1, 0, 1, 0}, dc = {0, 1, 0, -1};

    for (int t = 0; t < n * n; t++) {
        int idx = pos[t], r = idx / n, c = idx % n;
        open[idx] = true;

        for (int k = 0; k < 4; k++) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr >= 0 && nr < n && nc >= 0 && nc < n && open[nr * n + nc])
                dsu.union(idx, nr * n + nc);
        }
        if (dsu.connected(0, n * n - 1)) return t;
    }
    return -1;
}

private int timer = 0;

public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (List<Integer> e : connections) {
        adj.get(e.get(0)).add(e.get(1));
        adj.get(e.get(1)).add(e.get(0));
    }

    int[] tin = new int[n], low = new int[n];
    boolean[] vis = new boolean[n];
    List<List<Integer>> bridges = new ArrayList<>();

    dfs(0, -1, adj, vis, tin, low, bridges);
    return bridges;
}

private void dfs(int u, int parent, List<List<Integer>> adj, boolean[] vis,
                 int[] tin, int[] low, List<List<Integer>> bridges) {
    vis[u] = true;
    tin[u] = low[u] = timer++;

    for (int v : adj.get(u)) {
        if (v == parent) continue;

        if (!vis[v]) {
            dfs(v, u, adj, vis, tin, low, bridges);
            low[u] = Math.min(low[u], low[v]);          // child se

            if (low[v] > tin[u]) {                      // *** BRIDGE ***
                bridges.add(Arrays.asList(u, v));
            }
        } else {
            low[u] = Math.min(low[u], tin[v]);          // back edge — tin, low nahi
        }
    }
}

private int timer = 0;

public List<Integer> articulationPoints(int V, List<List<Integer>> adj) {
    int[] tin = new int[V], low = new int[V];
    boolean[] vis = new boolean[V], isAP = new boolean[V];

    for (int i = 0; i < V; i++)
        if (!vis[i]) dfs(i, -1, adj, vis, tin, low, isAP);

    List<Integer> res = new ArrayList<>();
    for (int i = 0; i < V; i++) if (isAP[i]) res.add(i);
    return res.isEmpty() ? Arrays.asList(-1) : res;
}

private void dfs(int u, int parent, List<List<Integer>> adj, boolean[] vis,
                 int[] tin, int[] low, boolean[] isAP) {
    vis[u] = true;
    tin[u] = low[u] = timer++;
    int children = 0;

    for (int v : adj.get(u)) {
        if (v == parent) continue;

        if (!vis[v]) {
            dfs(v, u, adj, vis, tin, low, isAP);
            low[u] = Math.min(low[u], low[v]);

            if (low[v] >= tin[u] && parent != -1) isAP[u] = true;   // non-root
            children++;
        } else {
            low[u] = Math.min(low[u], tin[v]);
        }
    }

    if (parent == -1 && children > 1) isAP[u] = true;                // root rule
}

public int kosaraju(int V, List<List<Integer>> adj) {
    // STEP 1: finish order
    boolean[] vis = new boolean[V];
    Deque<Integer> st = new ArrayDeque<>();
    for (int i = 0; i < V; i++) if (!vis[i]) dfs1(i, adj, vis, st);

    // STEP 2: transpose
    List<List<Integer>> rev = new ArrayList<>();
    for (int i = 0; i < V; i++) rev.add(new ArrayList<>());
    for (int u = 0; u < V; u++)
        for (int v : adj.get(u)) rev.get(v).add(u);

    // STEP 3: stack order me DFS on reversed
    Arrays.fill(vis, false);
    int scc = 0;
    while (!st.isEmpty()) {
        int node = st.pop();
        if (!vis[node]) { scc++; dfs2(node, rev, vis); }
    }
    return scc;
}

private void dfs1(int u, List<List<Integer>> adj, boolean[] vis, Deque<Integer> st) {
    vis[u] = true;
    for (int v : adj.get(u)) if (!vis[v]) dfs1(v, adj, vis, st);
    st.push(u);                       // return ke waqt
}

private void dfs2(int u, List<List<Integer>> rev, boolean[] vis) {
    vis[u] = true;
    for (int v : rev.get(u)) if (!vis[v]) dfs2(v, rev, vis);
}

private int timer = 0;
private int[] tin, low;
private boolean[] onStack;
private Deque<Integer> st;
private List<List<Integer>> sccs;

public List<List<Integer>> tarjan(int V, List<List<Integer>> adj) {
    tin = new int[V]; low = new int[V];
    Arrays.fill(tin, -1);
    onStack = new boolean[V];
    st = new ArrayDeque<>();
    sccs = new ArrayList<>();

    for (int i = 0; i < V; i++) if (tin[i] == -1) dfs(i, adj);
    return sccs;
}

private void dfs(int u, List<List<Integer>> adj) {
    tin[u] = low[u] = timer++;
    st.push(u);
    onStack[u] = true;

    for (int v : adj.get(u)) {
        if (tin[v] == -1) {                        // abhi tak visit nahi
            dfs(v, adj);
            low[u] = Math.min(low[u], low[v]);
        } else if (onStack[v]) {                   // *** stack pe hai tabhi ***
            low[u] = Math.min(low[u], tin[v]);
        }
    }

    if (low[u] == tin[u]) {                        // SCC root
        List<Integer> comp = new ArrayList<>();
        while (true) {
            int w = st.pop();
            onStack[w] = false;
            comp.add(w);
            if (w == u) break;
        }
        sccs.add(comp);
    }
}

int count = 0;
for (int i = 0; i < n; i++) {
    if (!vis[i] && relevant(i)) {
        count++;
        flood(i);          // BFS ya DFS — poora component mark kar de
    }
}

dist[src] = 0;
pq.add(new int[]{0, src});
while (!pq.isEmpty()) {
    int[] cur = pq.poll();
    int d = cur[0], u = cur[1];
    if (d > dist[u]) continue;

    for (int[] nb : adj[u]) {
        int v = nb[0], wt = nb[1];
        int nd = COMBINE(d, wt);          // sum → normal | max → minimax
        if (nd < dist[v]) {
            dist[v] = nd;
            pq.add(new int[]{nd, v});
        }
    }
}