# python — Post-order distance-bucket aggregation (LC 1530)
# time  = O(N * distance^2)   distance^2 from the d1/d2 double loop per node
# space = O(N)                recursion depth + O(distance) bucket per frame
class Solution:
    def countPairs(self, root, distance):
        self.ans = 0

        def post_order(node):
            # cnt[d] = number of leaves exactly d edges below `node`
            if not node:
                return [0] * (distance + 1)
            if not node.left and not node.right:      # leaf: distance 0 to itself
                base = [0] * (distance + 1)
                base[0] = 1
                return base

            left  = post_order(node.left)
            right = post_order(node.right)

            # (1) join a left-leaf and a right-leaf THROUGH this node (their LCA)
            for d1 in range(distance + 1):
                for d2 in range(distance + 1):
                    if d1 + d2 + 2 <= distance:       # +2 for the two edges via node
                        self.ans += left[d1] * right[d2]

            # (2) shift up by 1 edge for the parent's view
            cur = [0] * (distance + 1)
            for d in range(distance):                 # d+1 must stay in bounds
                cur[d + 1] = left[d] + right[d]
            return cur

        post_order(root)
        return self.ans

def dfs(node, visited=None):
    """
    Universal DFS template for trees and graphs
    Can be adapted for various problems
    """
    # Base case
    if not node or (visited and node in visited):
        return
    
    # Mark as visited (for graphs)
    if visited is not None:
        visited.add(node)
    
    # Process current node (pre-order position)
    process(node)
    
    # Recursive calls
    for neighbor in get_neighbors(node):
        dfs(neighbor, visited)
    
    # Post-order processing if needed
    # process_after(node)

# Preorder: Root -> Left -> Right
def preorder(root):
    if not root:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)

# Inorder: Left -> Root -> Right  
def inorder(root):
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

# Postorder: Left -> Right -> Root
def postorder(root):
    if not root:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]

# Iterative with Stack
def dfs_iterative(root):
    if not root:
        return []
    
    stack = [root]
    result = []
    
    while stack:
        node = stack.pop()
        result.append(node.val)
        # Add right first so left is processed first (LIFO)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    
    return result

def dfs_graph(graph, start):
    """
    DFS for graph with cycle handling
    """
    visited = set()
    result = []
    
    def dfs(node):
        if node in visited:
            return
        
        visited.add(node)
        result.append(node)
        
        for neighbor in graph[node]:
            dfs(neighbor)
    
    dfs(start)
    return result

# For detecting cycles
def has_cycle(graph):
    visited = set()
    rec_stack = set()
    
    def dfs(node):
        visited.add(node)
        rec_stack.add(node)
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                if dfs(neighbor):
                    return True
            elif neighbor in rec_stack:
                return True
        
        rec_stack.remove(node)
        return False
    
    for node in graph:
        if node not in visited:
            if dfs(node):
                return True
    return False

def find_paths(root, target):
    """
    Find all root-to-leaf paths with sum = target
    """
    def dfs(node, curr_sum, path, result):
        if not node:
            return
        
        # Update current state
        curr_sum += node.val
        path.append(node.val)
        
        # Check if leaf and target met
        if not node.left and not node.right:
            if curr_sum == target:
                result.append(path[:])
        
        # Explore children
        dfs(node.left, curr_sum, path, result)
        dfs(node.right, curr_sum, path, result)
        
        # Backtrack
        path.pop()
    
    result = []
    dfs(root, 0, [], result)
    return result

def backtrack_template(candidates, target):
    """
    General backtracking template
    """
    def backtrack(start, path, remaining):
        # Base case - found solution
        if remaining == 0:
            result.append(path[:])
            return
        
        # Try all possibilities
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                continue
            
            # Make choice
            path.append(candidates[i])
            
            # Recurse
            backtrack(i, path, remaining - candidates[i])
            
            # Undo choice (backtrack)
            path.pop()
    
    result = []
    backtrack(0, [], target)
    return result

def modify_tree(root, condition):
    """
    Modify tree structure based on condition
    """
    if not root:
        return None
    
    # Recursively modify subtrees first
    root.left = modify_tree(root.left, condition)
    root.right = modify_tree(root.right, condition)
    
    # Modify current node based on condition
    if not condition(root):
        # Example: delete node, return child
        if not root.left:
            return root.right
        if not root.right:
            return root.left
        # Handle two children case
        # ... (find successor/predecessor)
    
    return root

def bottom_up_dfs(root):
    """
    Process subtrees first, then current node
    Useful for subtree problems
    """
    def dfs(node):
        if not node:
            return 0  # or base value

        # Process subtrees first
        left_result = dfs(node.left)
        right_result = dfs(node.right)

        # Process current node using subtree results
        current_result = process(node, left_result, right_result)

        # Update global result if needed
        self.global_result = max(self.global_result, current_result)

        return current_result

    self.global_result = 0
    dfs(root)
    return self.global_result

def two_pass_dfs(grid):
    """
    Two-pass approach for grid problems
    Pass 1: Eliminate boundary-connected cells
    Pass 2: Count/process remaining valid cells
    Common for "closed" or "surrounded" problems
    """
    if not grid or not grid[0]:
        return 0

    rows, cols = len(grid), len(grid[0])

    def flood(r, c):
        """Mark cell and all connected cells as visited"""
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != target:
            return
        grid[r][c] = marked  # Mark as visited
        # Visit 4 neighbors
        flood(r + 1, c)
        flood(r - 1, c)
        flood(r, c + 1)
        flood(r, c - 1)

    # Pass 1: Eliminate boundary-connected cells
    # Top and bottom borders
    for c in range(cols):
        flood(0, c)
        flood(rows - 1, c)

    # Left and right borders
    for r in range(rows):
        flood(r, 0)
        flood(r, cols - 1)

    # Pass 2: Count/process remaining valid cells
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == target:
                count += 1
                flood(r, c)  # Mark to avoid double counting

    return count

// Java implementation
public int twoPassDFS(int[][] grid) {
    if (grid == null || grid.length == 0) {
        return 0;
    }

    int rows = grid.length;
    int cols = grid[0].length;

    // Pass 1: Eliminate boundary-connected cells
    for (int c = 0; c < cols; c++) {
        flood(grid, 0, c);           // Top border
        flood(grid, rows - 1, c);    // Bottom border
    }

    for (int r = 0; r < rows; r++) {
        flood(grid, r, 0);           // Left border
        flood(grid, r, cols - 1);    // Right border
    }

    // Pass 2: Count remaining valid cells
    int count = 0;
    for (int r = 1; r < rows - 1; r++) {
        for (int c = 1; c < cols - 1; c++) {
            if (grid[r][c] == 0) {
                count++;
                flood(grid, r, c);
            }
        }
    }

    return count;
}

private void flood(int[][] grid, int r, int c) {
    int rows = grid.length;
    int cols = grid[0].length;

    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] == 1) {
        return;
    }

    grid[r][c] = 1;  // Mark as visited

    // Visit 4 neighbors
    int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    for (int[] dir : dirs) {
        flood(grid, r + dir[0], c + dir[1]);
    }
}

def count_distinct_shapes(grid):
    """
    Count distinct island shapes using path signatures
    Key: Encode each island's shape as a unique string
    """
    if not grid or not grid[0]:
        return 0

    rows, cols = len(grid), len(grid[0])
    unique_shapes = set()

    def dfs(r, c, r0, c0, path):
        """
        DFS with path signature encoding
        r0, c0: Starting position for relative encoding
        path: StringBuilder to record the shape signature
        """
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != 1:
            return

        # Mark as visited
        grid[r][c] = 0

        # Encode relative position
        path.append(f"({r - r0},{c - c0})")

        # Visit neighbors in FIXED order (critical for consistency)
        dfs(r + 1, c, r0, c0, path)  # Down
        dfs(r - 1, c, r0, c0, path)  # Up
        dfs(r, c + 1, r0, c0, path)  # Right
        dfs(r, c - 1, r0, c0, path)  # Left

    # Iterate through grid in fixed order (top-left to bottom-right)
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                path = []
                dfs(r, c, r, c, path)  # Start with (r, c) as origin
                unique_shapes.add(tuple(path))

    return len(unique_shapes)

// Java implementation with directional encoding
public int numDistinctIslands(int[][] grid) {
    if (grid == null || grid.length == 0 || grid[0].length == 0) {
        return 0;
    }

    Set<String> uniqueIslandShapes = new HashSet<>();
    int rows = grid.length;
    int cols = grid[0].length;

    // Iterate through every cell in the grid
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            // Start DFS only on unvisited land cells
            if (grid[r][c] == 1) {
                StringBuilder pathSignature = new StringBuilder();
                // Start DFS from (r, c). 'S' marks the start
                dfs(grid, r, c, pathSignature, 'S');

                if (pathSignature.length() > 0) {
                    uniqueIslandShapes.add(pathSignature.toString());
                }
            }
        }
    }

    return uniqueIslandShapes.size();
}

/**
 * DFS with directional encoding
 * Records the direction taken to reach each cell
 * Uses 'O' delimiter when backtracking
 */
private void dfs(int[][] grid, int r, int c, StringBuilder path, char direction) {
    int rows = grid.length;
    int cols = grid[0].length;

    // Base cases: Out of bounds or water/visited
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] == 0) {
        return;
    }

    // 1. Mark as visited by setting to 0
    grid[r][c] = 0;

    // 2. Record the direction taken to reach this cell
    path.append(direction);

    // 3. Recurse in FIXED order (Down, Up, Right, Left)
    dfs(grid, r + 1, c, path, 'D');  // Down
    dfs(grid, r - 1, c, path, 'U');  // Up
    dfs(grid, r, c + 1, path, 'R');  // Right
    dfs(grid, r, c - 1, path, 'L');  // Left

    // 4. Add delimiter when backtracking
    // This distinguishes different branch structures
    path.append('O');
}

// Alternative: Relative coordinate encoding
public int numDistinctIslands_v2(int[][] grid) {
    if (grid == null || grid.length == 0) return 0;
    int rows = grid.length, cols = grid[0].length;
    boolean[][] seen = new boolean[rows][cols];
    Set<String> shapes = new HashSet<>();

    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (!seen[r][c] && grid[r][c] == 1) {
                StringBuilder sb = new StringBuilder();
                dfs(grid, seen, r, c, r, c, sb);
                shapes.add(sb.toString());
            }
        }
    }
    return shapes.size();
}

/**
 * DFS with relative coordinate encoding
 * Records relative positions from starting point
 */
private void dfs(int[][] grid, boolean[][] seen, int r0, int c0, int r, int c, StringBuilder sb) {
    int rows = grid.length, cols = grid[0].length;
    if (r < 0 || r >= rows || c < 0 || c >= cols) return;
    if (seen[r][c] || grid[r][c] != 1) return;

    seen[r][c] = true;
    // Record relative position from origin (r0, c0)
    sb.append((r - r0)).append('_').append((c - c0)).append(',');

    // Visit in fixed order
    dfs(grid, seen, r0, c0, r + 1, c, sb);
    dfs(grid, seen, r0, c0, r - 1, c, sb);
    dfs(grid, seen, r0, c0, r, c + 1, sb);
    dfs(grid, seen, r0, c0, r, c - 1, sb);
}

/**
 * Pattern: DFS traversal on one grid while validating against another grid
 * Use case: Count sub-islands, validate subset components, inclusion checking
 * Key insight: Use boolean flag propagation to track whether ALL cells satisfy condition
 *
 * Time: O(m × n) - visit each cell once
 * Space: O(m × n) - recursion stack + visited set
 */
public int countSubComponents(int[][] grid1, int[][] grid2) {
    if (grid2 == null || grid2.length == 0) {
        return 0;
    }

    int rows = grid2.length;
    int cols = grid2[0].length;
    Set<Integer> visited = new HashSet<>();
    int count = 0;

    // Iterate through grid2 to find all components
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            int flatCoord = r * cols + c;

            // Start DFS on unvisited land cells in grid2
            if (grid2[r][c] == 1 && !visited.contains(flatCoord)) {
                // DFS returns true if ALL cells in this component exist in grid1
                if (dfsValidate(grid1, grid2, r, c, visited)) {
                    count++;
                }
            }
        }
    }

    return count;
}

/**
 * DFS with validation: Check if entire component in grid2 is subset of grid1
 * Returns true only if ALL cells in the component satisfy the condition
 */
private boolean dfsValidate(int[][] grid1, int[][] grid2, int r, int c, Set<Integer> visited) {
    int rows = grid2.length;
    int cols = grid2[0].length;
    int flatCoord = r * cols + c;

    // Base cases
    if (r < 0 || r >= rows || c < 0 || c >= cols
        || grid2[r][c] == 0 || visited.contains(flatCoord)) {
        return true; // Empty/visited cells don't violate the condition
    }

    // Mark as visited
    visited.add(flatCoord);

    // Initialize result as true
    boolean isValid = true;

    // Check condition: Does this cell exist in grid1?
    if (grid1[r][c] == 0) {
        isValid = false; // Found a cell in grid2 that's NOT in grid1
    }

    // CRITICAL: Use && with res to propagate validation through entire component
    // Must visit ALL neighbors even if isValid is false (to mark them as visited)
    isValid = dfsValidate(grid1, grid2, r - 1, c, visited) && isValid;
    isValid = dfsValidate(grid1, grid2, r + 1, c, visited) && isValid;
    isValid = dfsValidate(grid1, grid2, r, c - 1, visited) && isValid;
    isValid = dfsValidate(grid1, grid2, r, c + 1, visited) && isValid;

    return isValid;
}

def count_sub_components(grid1, grid2):
    """
    Count components in grid2 that are completely contained in grid1
    """
    if not grid2 or not grid2[0]:
        return 0

    rows, cols = len(grid2), len(grid2[0])
    visited = set()
    count = 0

    def dfs(r, c):
        """
        DFS with validation
        Returns True if entire component is valid
        """
        # Base cases
        if (r < 0 or r >= rows or c < 0 or c >= cols
            or grid2[r][c] == 0 or (r, c) in visited):
            return True

        visited.add((r, c))

        # Check condition
        is_valid = True
        if grid1[r][c] == 0:
            is_valid = False

        # Visit all neighbors (must visit ALL even if invalid)
        is_valid = dfs(r - 1, c) and is_valid
        is_valid = dfs(r + 1, c) and is_valid
        is_valid = dfs(r, c - 1) and is_valid
        is_valid = dfs(r, c + 1) and is_valid

        return is_valid

    # Main loop
    for r in range(rows):
        for c in range(cols):
            if grid2[r][c] == 1 and (r, c) not in visited:
                if dfs(r, c):
                    count += 1

    return count

Problem: Count islands in grid2 that are completely contained in grid1

grid1: [[1,1,1,0,0],    grid2: [[1,1,1,0,0],
        [0,1,1,1,1],            [0,0,1,0,0],
        [0,0,0,0,0],            [0,1,0,0,0],
        [1,0,0,0,0],            [1,0,1,1,0],
        [1,1,0,1,1]]            [0,1,0,1,0]]

Analysis:
- Island 1 in grid2 (top-left): Cells (0,0), (0,1), (0,2), (1,2)
  → Check grid1: All exist? YES → Count it ✓

- Island 2 in grid2 (middle): Cells (2,1)
  → Check grid1: (2,1) = 0 → NOT a sub-island ✗

- Island 3 in grid2 (bottom): Cells (3,0), (3,2), (3,3), (4,1), (4,3)
  → Check grid1: (3,0) = 1, but (4,1) = 1... complex shape
  → Some cells don't match → NOT a sub-island ✗

Result: 1 sub-island (only the first one)

Key Insight:
- Must traverse ENTIRE island in grid2
- Check EVERY cell against grid1
- Return true only if ALL cells pass validation

// CORRECT: Visit all neighbors, accumulate results
res = dfs(r - 1, c) && res;
res = dfs(r + 1, c) && res;
res = dfs(r, c - 1) && res;
res = dfs(r, c + 1) && res;

// WRONG: Short-circuits, doesn't visit all cells
if (!dfs(r - 1, c)) return false;  // Stops early, leaves cells unvisited!

/**
 * Pattern: Build bidirectional graph with direction flags, count edge reversals via DFS
 * Use case: Reorder edges, reverse routes, make all paths lead to a target node
 * Key insight: Treat directed graph as undirected for traversal, but track original directions
 *
 * Time: O(V + E) - visit each node and edge once
 * Space: O(V + E) - adjacency list + visited array
 */
public int minReorder(int n, int[][] connections) {
    // Build bidirectional adjacency list with direction flags
    // Map: city -> List of [neighbor, direction_flag]
    // direction_flag: 1 if original direction (needs reversal)
    // direction_flag: 0 if reverse direction (correct direction)
    Map<Integer, List<int[]>> adj = new HashMap<>();
    for (int i = 0; i < n; i++) {
        adj.put(i, new ArrayList<>());
    }

    for (int[] c : connections) {
        int from = c[0];
        int to = c[1];

        // Original direction: from -> to (flag = 1, needs reversal)
        adj.get(from).add(new int[]{to, 1});

        // Reverse direction: to -> from (flag = 0, correct direction)
        adj.get(to).add(new int[]{from, 0});
    }

    boolean[] visited = new boolean[n];
    int[] count = {0}; // Use array to pass by reference

    // Start DFS from target node (city 0)
    dfsCountReversals(0, adj, visited, count);

    return count[0];
}

/**
 * DFS to count edges that need reversal
 * Increment count when traversing edge with flag=1 (wrong direction)
 */
private void dfsCountReversals(int node, Map<Integer, List<int[]>> adj,
                                boolean[] visited, int[] count) {
    visited[node] = true;

    for (int[] edge : adj.get(node)) {
        int neighbor = edge[0];
        int directionFlag = edge[1];

        if (!visited[neighbor]) {
            // If flag = 1, edge points away from target (needs reversal)
            if (directionFlag == 1) {
                count[0]++;
            }
            dfsCountReversals(neighbor, adj, visited, count);
        }
    }
}

def min_reorder(n, connections):
    """
    Count minimum edge reversals to make all paths lead to node 0
    """
    # Build bidirectional graph with direction flags
    adj = {i: [] for i in range(n)}

    for src, dst in connections:
        # Original direction: src -> dst (flag=1, needs reversal)
        adj[src].append((dst, 1))
        # Reverse direction: dst -> src (flag=0, correct)
        adj[dst].append((src, 0))

    visited = set()
    count = [0]

    def dfs(node):
        visited.add(node)

        for neighbor, flag in adj[node]:
            if neighbor not in visited:
                # If flag=1, edge points away from 0 (needs reversal)
                if flag == 1:
                    count[0] += 1
                dfs(neighbor)

    dfs(0)  # Start from target node
    return count[0]

/**
 * Pattern: Count pairs of nodes that cannot reach each other across different components
 * Use case: Count unreachable/disconnected pairs, isolated node pairs
 * Key insight: For each component, multiply its size by nodes in OTHER components
 *
 * Time: O(V + E) - DFS to find all components
 * Space: O(V) - visited array + adjacency list
 */

// Approach 1: DFS with Forward Counting (count against already processed)
public long countUnreachablePairs_DFS_Forward(int n, int[][] edges) {
    // Build adjacency list
    List<Integer>[] adj = new ArrayList[n];
    for (int i = 0; i < n; i++) {
        adj[i] = new ArrayList<>();
    }
    for (int[] edge : edges) {
        adj[edge[0]].add(edge[1]);
        adj[edge[1]].add(edge[0]);
    }

    boolean[] visited = new boolean[n];
    long totalUnreachablePairs = 0;
    long nodesProcessed = 0; // Track nodes in components already processed

    // Find each component and count pairs
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            // DFS to find component size
            long componentSize = dfs(i, adj, visited);

            /**
             * KEY TRICK: Forward counting
             * Each node in current component is unreachable from
             * ALL nodes in previous components
             *
             * Formula: componentSize × nodesProcessed
             * - componentSize: nodes in current component
             * - nodesProcessed: nodes in all previous components
             */
            totalUnreachablePairs += componentSize * nodesProcessed;

            // Update processed count
            nodesProcessed += componentSize;
        }
    }

    return totalUnreachablePairs;
}

private long dfs(int node, List<Integer>[] adj, boolean[] visited) {
    visited[node] = true;
    long count = 1;

    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) {
            count += dfs(neighbor, adj, visited);
        }
    }

    return count;
}

// Approach 2: Union-Find with Backward Counting (count against remaining unprocessed)
public long countUnreachablePairs_UnionFind_Backward(int n, int[][] edges) {
    // Initialize Union-Find
    int[] parent = new int[n];
    int[] rank = new int[n];
    for (int i = 0; i < n; i++) {
        parent[i] = i;
    }

    // Union all edges
    for (int[] edge : edges) {
        union(edge[0], edge[1], parent, rank);
    }

    // Count component sizes
    Map<Integer, Integer> sizeMap = new HashMap<>();
    for (int i = 0; i < n; i++) {
        int root = find(i, parent);
        sizeMap.put(root, sizeMap.getOrDefault(root, 0) + 1);
    }

    long result = 0;
    long processed = 0;

    /**
     * KEY TRICK: Backward counting
     * For each component, count pairs with ALL remaining unprocessed nodes
     *
     * Formula: size × (n - size - processed)
     * - size: nodes in current component
     * - n: total nodes
     * - processed: nodes in components already counted
     * - (n - size - processed): nodes in OTHER components not yet counted
     *
     * This avoids double counting by only counting forward to remaining components
     */
    for (int size : sizeMap.values()) {
        result += size * (n - size - processed);
        processed += size;
    }

    return result;
}

private int find(int x, int[] parent) {
    if (parent[x] != x) {
        parent[x] = find(parent[x], parent); // Path compression
    }
    return parent[x];
}

private void union(int x, int y, int[] parent, int[] rank) {
    int rootX = find(x, parent);
    int rootY = find(y, parent);

    if (rootX != rootY) {
        // Union by rank
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
}

// Approach 3: Alternative - Count total pairs minus reachable pairs
public long countUnreachablePairs_Alternative(int n, int[][] edges) {
    // Build adjacency list
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        adj.add(new ArrayList<>());
    }
    for (int[] edge : edges) {
        adj.get(edge[0]).add(edge[1]);
        adj.get(edge[1]).add(edge[0]);
    }

    /**
     * Total possible pairs = n × (n-1) / 2
     * Reachable pairs = sum of (componentSize × (componentSize-1) / 2) for each component
     * Unreachable pairs = Total - Reachable
     */
    long totalPairs = (long) n * (n - 1) / 2;
    boolean[] visited = new boolean[n];

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            long size = dfsCount(i, adj, visited);
            // Subtract reachable pairs within this component
            totalPairs -= (size * (size - 1)) / 2;
        }
    }

    return totalPairs;
}

private long dfsCount(int node, List<List<Integer>> adj, boolean[] visited) {
    visited[node] = true;
    long count = 1;

    for (int neighbor : adj.get(node)) {
        if (!visited[neighbor]) {
            count += dfsCount(neighbor, adj, visited);
        }
    }

    return count;
}

def count_unreachable_pairs_dfs(n, edges):
    """
    Count unreachable pairs using DFS with forward counting
    """
    # Build adjacency list
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    visited = [False] * n
    total_pairs = 0
    processed = 0

    def dfs(node):
        """DFS to count component size"""
        visited[node] = True
        count = 1
        for neighbor in adj[node]:
            if not visited[neighbor]:
                count += dfs(neighbor)
        return count

    # Find each component
    for i in range(n):
        if not visited[i]:
            component_size = dfs(i)

            # Key trick: multiply by already processed nodes
            total_pairs += component_size * processed
            processed += component_size

    return total_pairs


def count_unreachable_pairs_uf(n, edges):
    """
    Count unreachable pairs using Union-Find with backward counting
    """
    # Initialize Union-Find
    parent = list(range(n))

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(x, y):
        root_x, root_y = find(x), find(y)
        if root_x != root_y:
            parent[root_x] = root_y

    # Union all edges
    for u, v in edges:
        union(u, v)

    # Count component sizes
    from collections import Counter
    size_map = Counter(find(i) for i in range(n))

    result = 0
    processed = 0

    # Key trick: count against remaining unprocessed nodes
    for size in size_map.values():
        result += size * (n - size - processed)
        processed += size

    return result

# python — LC 1219
# GUARD lives at the top of the child → doubles as the recursion base case.
# Cleanest to reason about: you may call dfs() on ANY coordinate (even off-grid);
# the child rejects itself. Cost: every invalid neighbor still spends one call frame.
class Solution:
    def getMaximumGold(self, grid):
        self.max_gold = 0
        rows, cols = len(grid), len(grid[0])
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] > 0:
                    self.dfs(grid, r, c, 0)   # start value = 0
        return self.max_gold

    def dfs(self, grid, r, c, cur_gold):
        rows, cols = len(grid), len(grid[0])
        # (1) GUARD: out of bounds OR empty(0) OR visited(-1) → stop
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] <= 0:
            return
        cache = grid[r][c]
        cur_gold += cache                                  # (2) ACCUMULATE here
        self.max_gold = max(self.max_gold, cur_gold)       # (3) UPDATE MAX per cell entry
        grid[r][c] = -1                                    # mark visited
        # recurse into ALL 4 dirs unconditionally — guard filters at the top
        self.dfs(grid, r + 1, c, cur_gold)
        self.dfs(grid, r - 1, c, cur_gold)
        self.dfs(grid, r, c + 1, cur_gold)
        self.dfs(grid, r, c - 1, cur_gold)
        grid[r][c] = cache                                 # BACKTRACK: restore

# python — LC 1219
# GUARD is inline BEFORE each recursive call → no wasted frames on invalid neighbors.
# The launch loop's `if grid[y][x] > 0` validates the START cell (child no longer does).
class Solution:
    def getMaximumGold(self, grid):
        self.max_gold = 0
        L, W = len(grid), len(grid[0])
        for y in range(L):
            for x in range(W):
                if grid[y][x] > 0:
                    self.dfs(grid, x, y, grid[y][x])   # start value = the cell itself
        return self.max_gold

    def dfs(self, grid, x, y, cur_gold):
        L, W = len(grid), len(grid[0])
        self.max_gold = max(self.max_gold, cur_gold)   # (3) UPDATE MAX per cell entry — safe
        cache = grid[y][x]
        grid[y][x] = -1                                # mark visited
        moves = [[-1, 0], [1, 0], [0, 1], [0, -1]]
        for dx, dy in moves:
            x_, y_ = x + dx, y + dy
            # (1) GUARD before recursing  +  (2) ACCUMULATE at the call site
            if 0 <= x_ < W and 0 <= y_ < L and grid[y_][x_] > 0:
                self.dfs(grid, x_, y_, cur_gold + grid[y_][x_])
        grid[y][x] = cache                             # BACKTRACK: restore

# python — LC 1219
# Same structure as V0-2, BUT max_gold is updated INSIDE the loop (on `next_gold`),
# not at cell entry. Consequence: the entry cell is never scored by the DFS itself,
# so a lone gold cell with no gold neighbors would be missed → the launch loop must
# SEED max_gold with grid[y][x]. That extra dependency is exactly what makes it fragile.
class Solution:
    def getMaximumGold(self, grid):
        self.max_gold = 0
        L, W = len(grid), len(grid[0])
        for y in range(L):
            for x in range(W):
                if grid[y][x] > 0:
                    self.max_gold = max(self.max_gold, grid[y][x])  # ⚠️ REQUIRED seed
                    self.dfs(grid, x, y, grid[y][x])
        return self.max_gold

    def dfs(self, grid, x, y, cur_gold):
        L, W = len(grid), len(grid[0])
        cache = grid[y][x]
        grid[y][x] = -1                                # mark visited (once per frame)
        moves = [[-1, 0], [1, 0], [0, 1], [0, -1]]
        for dx, dy in moves:
            x_, y_ = x + dx, y + dy
            if 0 <= x_ < W and 0 <= y_ < L and grid[y_][x_] > 0:
                # NOTE: do NOT mark/unmark grid[y][x] here inside the loop.
                # Marking is per-cell-entry, not per-neighbor: the same cell is
                # explored by all 4 branches of THIS frame; re-marking each
                # iteration would corrupt the shared state.
                next_gold = cur_gold + grid[y_][x_]
                self.max_gold = max(self.max_gold, next_gold)   # (3) UPDATE MAX in loop
                self.dfs(grid, x_, y_, next_gold)
        grid[y][x] = cache                             # BACKTRACK: restore

// java
// LC 199
private TreeNode _dfs(TreeNode node){

    if (node == null){
        return null;
    }

    /** NOTE !!! no need to create global node, but can define inside the method */
    TreeNode root2 = node;
    root2.left = this._dfs(node.left);
    root2.right = this._dfs(node.right);

    /** NOTE !!! we need to return root as final step */
    return root2;
}

// java
// LC 701

// ...
public TreeNode insertIntoBST(TreeNode root, int val){
    // ...

    insertNodeHelper(root, val);
    return root;
}

public void insertNodeHelper(TreeNode root, int val) {
    // ...
    if(...){
        root.left = new TreeNode(val);
    }else{
        root.right = new TreeNode(val);
    }

    // ...
    return root;
}

// ... 

# python
# form I : tree transversal
def dfs(root, target):

    if root.val == target:
       # do sth

    if root.val < target:
       dfs(root.left, target)
       # do sth

    if root.val > target:
       dfs(root.right, target)
       # do sth

# form II : modify values in tree

# 669 Trim a Binary Search Tree
class Solution:
    def trimBST(self, root, L, R):
        if not root:
            return 
        # NOTICE HERE 
        # SINCE IT'S BST
        # SO if root.val < L, THE root.right MUST LARGER THAN L
        # SO USE self.trimBST(root.right, L, R) TO FIND THE NEXT "VALIDATE" ROOT AFTER TRIM
        # THE REASON USE self.trimBST(root.right, L, R) IS THAT MAYBE NEXT ROOT IS TRIMMED AS WELL, SO KEEP FINDING VIA RECURSION
        if root.val < L:
            return self.trimBST(root.right, L, R)
        # NOTICE HERE 
        # SINCE IT'S BST
        # SO if root.val > R, THE root.left MUST SMALLER THAN R
        # SO USE self.trimBST(root.left, L, R) TO FIND THE NEXT "VALIDATE" ROOT AFTER TRIM
        if root.val > R:
            return self.trimBST(root.left, L, R)
        root.left = self.trimBST(root.left, L, R)
        root.right = self.trimBST(root.right, L, R)
        return root 

# 701 Insert into a Binary Search Tree
class Solution(object):
    def insertIntoBST(self, root, val):
        """
        NOTE !!!
            1) we ALWAYS do op first, then do recursive
                -> e.g.
                        ...
                        if not root: 
                            return TreeNode(val)
                        if root.val < val:
                            root.right = self.insertIntoBST(root.right, val)
                        ...
        """
        if not root: 
            return TreeNode(val)

        if root.val < val: 
            root.right = self.insertIntoBST(root.right, val)

        elif root.val > val: 
            root.left = self.insertIntoBST(root.left, val)

        return root

# form III : check if a value exist in the BST

def dfs(root, value):
    if not root:
        return False
    if root.val == value:
        return True
    if root.val > value:
        return dfs(root.left, value) 
    if root.val < value:
        return dfs(root.right, value)

# form IV : check if duplicated SUBTREES in tree
# LC 652 Find Duplicate Subtrees
# python
m = collections.defaultdict(int)   # { subtree_signature : count }
def dfs(root, m, res):
    if not root:
        return "#"                  # null marker -> makes signature unambiguous

    ### NOTE : serialize CURRENT subtree (post-order) -> use signature as hash key
    # str(root.val) avoids int+str TypeError; "#" + commas avoid ambiguity (e.g. 1,12 vs 11,2)
    path = str(root.val) + "," + dfs(root.left, m, res) + "," + dfs(root.right, m, res)

    if m[path] == 1:                # seen exactly once before -> this is the 2nd time -> duplicate
        res.append(root)            # collect the ROOT NODE (not the path string)

    m[path] += 1
    return path                     # return signature so PARENT can build its own signature

Encoding rules (why each piece matters):
  "#"   -> null child       (distinguishes shapes: a node w/ 1 child vs 2)
  ","   -> field delimiter  (so vals "1,12" never collide with "11,2")
  post-order -> children serialized first, parent reuses their result
Complexity: O(n) nodes, but each signature is O(n) long -> O(n^2) time / space worst case.
  (Use an int-id map instead of raw strings to get true O(n) — see V2 in the .py file.)

// java
// LC 200

/** NOTE !!!! BELOW approach has same effect */

// V1

// private boolean _is_island(char[][] grid, int x, int y, boolean[][] seen){}

// ....
_is_island(grid, x+1, y, seen);
_is_island(grid, x-1, y, seen);
_is_island(grid, x, y+1, seen);
_is_island(grid, x, y-1, seen);
// ....

// V2
// private boolean _is_island_2(char[][] grid, int x, int y, boolean[][] seen) {}

int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

for (int[] dir : directions) {
    int newX = x + dir[0];
    int newY = y + dir[1];
    _is_island(grid, newX, newY, seen);
}

# we don't need to declare y,z in func, but we can use them in the func directly
# and can get the returned value as well, this trick is being used a lot in the dfs
def test():
    def func(x):
        print ("x = " + str(x) + " y = " + str(y))
        for i in range(3):
            z.append(i)

    x = 0
    y = 100
    z = []
    func(x)
test()
print (z)

# Example) Add 1 to all node.value in Binary tree?
def dfs(root):
    if not root:
        return 
    root.val += 1 
    dfs(root.left)
    dfs(root.right)

# Example) check if 2 Binary tree are the same ? 
def dfs(root1, root2):
    if root1 == root2 == None:
        return True 
    if root1 is not None and root2 is None:
        return False 
    if root1 is None and root2 is not None:
        return False 
    else:
        if root1.val != root2.value:
            return False 
    return dfs(root1.left, root2.left) \
           and dfs(root1.right, root2.right)

# Example) check if a value exist in the BST
def dfs(root, value):
    if not root:
        return False
    if root.val == value:
        return True
    return dfs(root.left, value) or dfs(root.right, value)

# optimized : BST prpoerty :  root.right > root.val > root.left
def dfs(root, value):
    if not root:
        return False
    if root.val == value:
        return True
    if root.val > value:
        return dfs(root.left, value) 
    if root.val < value:
        return dfs(root.right, value)

# get sum of sub tree
# LC 508 Most Frequent Subtree Sum
def get_sum(root):
    if not root:
        return 0
    ### NOTE THIS !!!
    #  -> we need to do get_sum(root.left), get_sum(root.right) on the same time
    s = get_sum(root.left) + root.val + get_sum(root.right)
    res.append(s)
    return s

# LC 663 Equal Tree Partition
# LC 508 Most Frequent Subtree Sum
seen = []
def _sum(root):
    if not root:
        return 0
    seen.append( root.val + _sum(root.left) + _sum(root.right) )

# Convert BST to Greater Tree 
# LC 538
_sum = 0
def dfs(root):
    dfs(root.right)
    _sum += root.val
    root.val = _sum
    dfs(root.left)

# LC 297. Serialize and Deserialize Binary Tree
# please check below 2) LC Example
# V0
# IDRA : DFS
class Codec:

    def serialize(self, root):
        """ Encodes a tree to a single string.
        :type root: TreeNode
        :rtype: str
        """
        def rserialize(root, string):
            """ a recursive helper function for the serialize() function."""
            # check base case
            if root is None:
                string += 'None,'
            else:
                string += str(root.val) + ','
                string = rserialize(root.left, string)
                string = rserialize(root.right, string)
            return string
        
        return rserialize(root, '')    

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        :type data: str
        :rtype: TreeNode
        """
        def rdeserialize(l):
            """ a recursive helper function for deserialization."""
            if l[0] == 'None':
                l.pop(0)
                return None
                
            root = TreeNode(l[0])
            l.pop(0)
            root.left = rdeserialize(l)
            root.right = rdeserialize(l)
            return root

        data_list = data.split(',')
        root = rdeserialize(data_list)
        return root

// java
// LC 297
public class Codec{
    public String serialize(TreeNode root) {

        /** NOTE !!!
         *
         *     if root == null, return "#"
         */
        if (root == null){
            return "#";
        }

        /** NOTE !!! return result via pre-order, split with "," */
        return root.val + "," + serialize(root.left) + "," + serialize(root.right);
    }

    public TreeNode deserialize(String data) {

        /** NOTE !!!
         *
         *   1) init queue and append serialize output
         *   2) even use queue, but helper func still using DFS
         */
        Queue<String> queue = new LinkedList<>(Arrays.asList(data.split(",")));
        return helper(queue);
    }

    private TreeNode helper(Queue<String> queue) {

        // get val from queue first
        String s = queue.poll();

        if (s.equals("#")){
            return null;
        }
        /** NOTE !!! init current node  */
        TreeNode root = new TreeNode(Integer.valueOf(s));
        /** NOTE !!!
         *
         *    since serialize is "pre-order",
         *    deserialize we use "pre-order" as well
         *    e.g. root -> left sub tree -> right sub tree
         *    -> so we get sub tree via below :
         *
         *       root.left = helper(queue);
         *       root.right = helper(queue);
         *
         */
        root.left = helper(queue);
        root.right = helper(queue);
        /** NOTE !!! don't forget to return final deserialize result  */
        return root;
    }
}

# LC 449. Serialize and Deserialize BST
# please check below 2) LC Example
# NOTE : there is also a bfs approach
# V1'
# IDEA : BST property
# https://leetcode.com/problems/serialize-and-deserialize-bst/discuss/212043/Python-solution
class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        def dfs(root):
            if not root:
                return 
            res.append(str(root.val) + ",")
            dfs(root.left)
            dfs(root.right)
            
        res = []
        dfs(root)
        return "".join(res)

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        lst = data.split(",")
        lst.pop()
        stack = []
        head = None
        for n in lst:
            n = int(n)
            if not head:
                head = TreeNode(n)
                stack.append(head)
            else:
                node = TreeNode(n)
                if n < stack[-1].val:
                    stack[-1].left = node
                else:
                    while stack and stack[-1].val < n: 
                        u = stack.pop()
                    u.right = node
                stack.append(node)
        return head

// java
// LC 543 Diameter of Binary Tree
// V1
// IDEA : DFS
// https://leetcode.com/problems/diameter-of-binary-tree/editorial/

int diameter;

public int diameterOfBinaryTree_2(TreeNode root) {
    diameter = 0;
    longestPath(root);
    return diameter;
}
private int longestPath(TreeNode node){
    if(node == null) return 0;
    // recursively find the longest path in
    // both left child and right child
    int leftPath = longestPath(node.left);
    int rightPath = longestPath(node.right);

    // update the diameter if left_path plus right_path is larger
    diameter = Math.max(diameter, leftPath + rightPath);

    // return the longest one between left_path and right_path;
    // remember to add 1 for the path connecting the node and its parent
    return Math.max(leftPath, rightPath) + 1;
}

// java
// LC 1448

private void dfsCheckGoodNode(TreeNode node, int maxSoFar) {
    if (node == null)
        return;

    // Check if the current node is good
    if (node.val >= maxSoFar) {
        res++;
        maxSoFar = node.val; // Update max value seen so far
    }

    // Recur for left and right children
    dfsCheckGoodNode(node.left, maxSoFar);
    dfsCheckGoodNode(node.right, maxSoFar);
}

# 098 Validate Binary Search Tree
### NOTE : there is also bfs solution
# https://github.com/yennanliu/CS_basics/blob/master/leetcode_python/Recursion/validate-binary-search-tree.py
class Solution(object):
    def isValidBST(self, root):
        return self.valid(root, float('-inf'), float('inf'))
        
    def valid(self, root, min_, max_):
        if not root: return True
        if root.val >= max_ or root.val <= min_:
            return False
        return self.valid(root.left, min_, root.val) and self.valid(root.right, root.val, max_)

// java
// LC 701

public TreeNode insertIntoBST_0_1(TreeNode root, int val) {
    if (root == null) {
        return new TreeNode(val);
    }

    /** 
     *  NOTE !!! 
     *  
     *   via below, we can still `MODIFY root value`,
     *   even it's not declared as a global variable
     *   
     *   -> e.g. we have root as input,
     *      within `insertNodeHelper` method,
     *      we append `new sub tree` to root as its left, right sub tree
     *
     */
    insertNodeHelper(root, val); // helper modifies the tree in-place
    return root;
}

public void insertNodeHelper(TreeNode root, int val) {
    if (val < root.val) {
        if (root.left == null) {
            root.left = new TreeNode(val);
        } else {
            /** NOTE !!!
             * 
             *  no need to return val,
             *  since we `append sub tree` to root directly
             *  in the method (e.g. root.left == ..., root.right = ...)
             */
            insertNodeHelper(root.left, val);
        }
    } else {
        if (root.right == null) {
            root.right = new TreeNode(val);
        } else {
            insertNodeHelper(root.right, val);
        }
    }
}

# 701 Insert into a Binary Search Tree

# VO : recursion + dfs
class Solution(object):
    def insertIntoBST(self, root, val):
        if not root: 
            return TreeNode(val)
        if root.val < val: 
            root.right = self.insertIntoBST(root.right, val);
        elif root.val > val: 
            root.left = self.insertIntoBST(root.left, val);
        return(root)

# 450 Delete Node in a BST
# V0
# IDEA : RECURSION + BST PROPERTY
#### 2 CASES :
#   -> CASE 1 : root.val == key and NO right subtree 
#                -> swap root and root.left, return root.left
#   -> CASE 2 : root.val == key and THERE IS right subtree
#                -> 1) go to 1st RIGHT sub tree
#                -> 2) iterate to deepest LEFT subtree
#                -> 3) swap root and  `deepest LEFT subtree` then return root
class Solution(object):
    def deleteNode(self, root, key):
        if not root: return None
        if root.val == key:
            # case 1 : NO right subtree 
            if not root.right:
                left = root.left
                return left
            # case 2 : THERE IS right subtree
            else:
                ### NOTE : find min in "right" sub-tree
                #           -> because BST property, we ONLY go to 1st right tree (make sure we find the min of right sub-tree)
                #           -> then go to deepest left sub-tree
                right = root.right
                while right.left:
                    right = right.left
                ### NOTE : we need to swap root, right ON THE SAME TIME
                root.val, right.val = right.val, root.val
        root.left = self.deleteNode(root.left, key)
        root.right = self.deleteNode(root.right, key)
        return root

// java
// LC 450
// V0
// IDEA: DFS + BST property
/**
 *
 * (when found a node to delete)
 *
 *    // Case 1: No children
 *
 *    // Case 2: One child
 *
 *    // Case 3: Two children
 *
 */
/**
 *
 *  Summary of Deletion Strategy:
 *
 *
 *  | Case         | Description        | What Happens                                  |
 * |--------------|--------------------|-----------------------------------------------|
 * | Leaf         | No children         | Return `null`                                 |
 * | One Child    | One child           | Replace node with its child                   |
 * | Two Children | Both children       | Replace with in-order successor, then delete the successor |
 *
 *
 *  `in-order successor`:  Left → root → Right
 */

public TreeNode deleteNode(TreeNode root, int key) {
    return deleteNodeHelper_0(root, key);
}

private TreeNode deleteNodeHelper_0(TreeNode root, int key) {
    if (root == null) {
        return null;
    }

    /**
     * CASE 1)  NOT found a node to delete
     */
    if (key < root.val) {
        // search in left subtree
        /**
         *  NOTE !!!
         *
         *   we assign `left sub tree` as res from deleteNodeHelper_0(root.left, key)
         *
         *   -> NOT return `deleteNodeHelper_0(root.left, key)`
         *      as res directly, since it deleteNodeHelper_0
         *      could NOT be a null val, we need it to assign root.left,
         *      so we can keep `whole BST info`
         */
        root.left = deleteNodeHelper_0(root.left, key);
    } else if (key > root.val) {
        // search in right subtree
        /**
         *  NOTE !!!
         *
         *   we assign `right sub tree` as res from deleteNodeHelper_0(root.right, key)
         */
        root.right = deleteNodeHelper_0(root.right, key);
    }
    /**
     * CASE 2)  Found a node to delete
     */
    else {
        // Case 1: No left child
        if (root.left == null) {
            return root.right;
        }

        // Case 2: No right child
        if (root.right == null) {
            return root.left;
        }

        /**
         *  NOTE !!!! below
         *
         *  step 1) find `min` val  (`sub right tree`)
         *  step 2) set root val as min val
         *  step 3)  delete the `min` val node from sub right tree
         *             - `recursively` call `deleteNodeHelper`
         *
         */
        // Case 3: Two children → find inorder successor
        /**
         *  NOTE !!!
         *
         *   we need to find a `min` tree from `sub right tree`
         *   as a node to `swap` with current node.
         *
         *   Reason:
         *      since it is a BST, so  `left < root < right`.
         *      so after swapping `min` from sub right tree.
         *      with current node
         *          -> the tree `remains` BST.
         *          we DON'T have to do any further modification.
         *
         */
        TreeNode minNode = findMin_0(root.right);
        root.val = minNode.val; // copy value
        root.right = deleteNodeHelper(root.right, minNode.val); // delete successor
    }

    return root;
}

private TreeNode findMin_0(TreeNode node) {
    while (node.left != null) {
        node = node.left;
    }
    return node;
}

# 652 Find Duplicate Subtrees
import collections
class Solution(object):
    def findDuplicateSubtrees(self, root):
        res = []
        m = collections.defaultdict(int)
        self.dfs(root, m, res)
        return res

    def dfs(self, root, m, res):
        if not root:
            return '#'
        path = str(root.val) + '-' + self.dfs(root.left, m, res) + '-' + self.dfs(root.right, m, res)
        if m[path] == 1:
            res.append(root) 
        m[path] += 1
        return path

# 669 Trim a Binary Search Tree
class Solution:
    def trimBST(self, root, L, R):
        if not root:
            return None
        if root.val > R:
            return self.trimBST(root.left, L, R)
        elif root.val < L:
            return self.trimBST(root.right, L, R)
        else:
            root.left = self.trimBST(root.left, L, R)
            root.right = self.trimBST(root.right, L, R)
            return root

# 662 Maximum Width of Binary Tree
class Solution(object):
    def widthOfBinaryTree(self, root):
        self.ans = 0
        left = {}
        def dfs(node, depth = 0, pos = 0):
            if node:
                left.setdefault(depth, pos)
                self.ans = max(self.ans, pos - left[depth] + 1)
                dfs(node.left, depth + 1, pos * 2)
                dfs(node.right, depth + 1, pos * 2 + 1)

        dfs(root)
        return self.ans

# 663 Equal Tree Partition
# V0
# IDEA : DFS + cache
class Solution(object):
    def checkEqualTree(self, root):
        seen = []

        def sum_(node):
            if not node: return 0
            seen.append(sum_(node.left) + sum_(node.right) + node.val)
            return seen[-1]

        sum_(root)
        #print ("seen = " + str(seen))
        return seen[-1] / 2.0 in seen[:-1]

# V0'
class Solution(object):
    def checkEqualTree(self, root):
        seen = []

        def sum_(node):
            if not node: return 0
            seen.append(sum_(node.left) + sum_(node.right) + node.val)
            return seen[-1]
            
        total = sum_(root)
        seen.pop()
        return total / 2.0 in seen

# 776 Split BST
# V0
# IDEA : BST properties (left < root < right) + recursion
# https://blog.csdn.net/magicbean2/article/details/79679927
# https://www.itdaan.com/tw/d58594b92742689b5769f9827365e8b4
### STEPS
#  -> 1) check whether root.val > or < V
#     -> if root.val > V : 
#           - NO NEED TO MODIFY ALL RIGHT SUB TREE
#           - BUT NEED TO re-connect nodes in LEFT SUB TREE WHICH IS BIGGER THAN V (root.left = right)
#     -> if root.val < V : 
#           - NO NEED TO MODIFY ALL LEFT SUB TREE
#           - BUT NEED TO re-connect nodes in RIGHT SUB TREE WHICH IS SMALLER THAN V (root.right = left)
# -> 2) return result
class Solution(object):
    def splitBST(self, root, V):
        if not root: return [None, None]
        ### NOTE : if root.val <= V
        if root.val > V:
            left, right = self.splitBST(root.left, V)
            root.left = right
            return [left, root]
        ### NOTE : if root.val > V
        else:
            left, right = self.splitBST(root.right, V)
            root.right = left
            return [root, right]

# 399 Evaluate Division
# there is also an "union find" solution
class Solution:
    def calcEquation(self, equations, values, queries):
        from collections import defaultdict
        # build graph
        graph = defaultdict(dict)
        for (x, y), v in zip(equations, values):
            graph[x][y] = v
            graph[y][x] = 1.0/v
        ans = [self.dfs(x, y, graph, set()) for (x, y) in queries]
        return ans

    def dfs(self, x, y, graph, visited):
        if not graph:
            return
        if x not in graph or y not in graph:
            return -1
        if x == y:
            return 1
        visited.add(x)
        for n in graph[x]:
            if n in visited:
                continue
            visited.add(n)
            d = self.dfs(n, y, graph, visited)
            if d > 0:
                return d * graph[x][n]
        return -1.0

// java
// V1
// IDEA: DFS
// https://leetcode.com/problems/evaluate-division/solutions/3543256/image-explanation-easiest-concise-comple-okpu/
public double[] calcEquation_1(List<List<String>> equations, double[] values, List<List<String>> queries) {
    HashMap<String, HashMap<String, Double>> gr = buildGraph(equations, values);
    double[] finalAns = new double[queries.size()];

    for (int i = 0; i < queries.size(); i++) {
        String dividend = queries.get(i).get(0);
        String divisor = queries.get(i).get(1);

        /** NOTE !!!
         *
         *  either dividend nor divisor NOT in graph, return -1.0 directly
         */
        if (!gr.containsKey(dividend) || !gr.containsKey(divisor)) {
            finalAns[i] = -1.0;
        } else {

            /** NOTE !!!
             *
             *  we use `vis` to check if element already visited
             *  (to avoid repeat accessing)
             *  `vis` init again in every loop
             */

            HashSet<String> vis = new HashSet<>();
            /**
             *  NOTE !!!
             *
             *   we init `ans` and pass it to dfs method
             *   (but dfs method return NOTHING)
             *   -> `ans` is init, and pass into dfs,
             *   -> so `ans` value is updated during dfs recursion run
             *   -> and after dfs run completed, we get the result `ans` value
             */
            double[] ans = { -1.0 };
            double temp = 1.0;
            dfs(dividend, divisor, gr, vis, ans, temp);
            finalAns[i] = ans[0];
        }
    }

    return finalAns;
}

/** NOTE !!! below dfs method */
public void dfs(String node, String dest, HashMap<String, HashMap<String, Double>> gr, HashSet<String> vis,
                double[] ans, double temp) {

    /** NOTE !!! we use `vis` to check if element already visited */
    if (vis.contains(node))
        return;

    vis.add(node);
    if (node.equals(dest)) {
        ans[0] = temp;
        return;
    }

    for (Map.Entry<String, Double> entry : gr.get(node).entrySet()) {
        String ne = entry.getKey();
        double val = entry.getValue();
        /** NOTE !!! update temp as `temp * val` */
        dfs(ne, dest, gr, vis, ans, temp * val);
    }
}

public HashMap<String, HashMap<String, Double>> buildGraph(List<List<String>> equations, double[] values) {
    HashMap<String, HashMap<String, Double>> gr = new HashMap<>();

    for (int i = 0; i < equations.size(); i++) {
        String dividend = equations.get(i).get(0);
        String divisor = equations.get(i).get(1);
        double value = values[i];

        gr.putIfAbsent(dividend, new HashMap<>());
        gr.putIfAbsent(divisor, new HashMap<>());

        gr.get(dividend).put(divisor, value);
        gr.get(divisor).put(dividend, 1.0 / value);
    }

    return gr;
}

# LC 508 Most Frequent Subtree Sum
# V0
# IDEA : DFS + TREE
class Solution(object):
    def findFrequentTreeSum(self, root):
        """
        ### NOTE : this trick : get sum of sub tree
        # LC 663 Equal Tree Partition
        """
        def get_sum(root):
            if not root:
                return 0
            s = get_sum(root.left) + root.val + get_sum(root.right)
            res.append(s)
            return s

        if not root:
            return []
        res = []
        get_sum(root)
        counts = collections.Counter(res)
        _max = max(counts.values())
        return [x for x in counts if counts[x] == _max]

# V0'
# IDEA : DFS + COUNTER
from collections import Counter
class Solution(object):
    def findFrequentTreeSum(self, root):
        def helper(root, d):
            if not root:
                return 0
            left = helper(root.left, d)
            right = helper(root.right, d)
            subtreeSum = left + right + root.val
            d[subtreeSum] = d.get(subtreeSum, 0) + 1
            return subtreeSum      
        d = {}
        helper(root, d)
        mostFreq = 0
        ans = []
        print ("d = " + str(d))
        _max_cnt = max(d.values())
        ans = []
        return [x for x in d if d[x] == _max_cnt]

# LC 538 Convert BST to Greater Tree
# V0
# IDEA : DFS + recursion
#      -> NOTE : via DFS, the op will being executed in `INVERSE` order (last visit will be run first, then previous, then ...)
#      -> e.g. node1 -> node2 -> ... nodeN
#      ->      will run nodeN -> nodeN-1 ... node1
class Solution(object):

    def convertBST(self, root):
        self.sum = 0
        self.dfs(root)
        return root

    def dfs(self, node):
        if not node: 
            return
        #print ("node.val = " + str(node.val))
        self.dfs(node.right)
        self.sum += node.val
        node.val = self.sum
        self.dfs(node.left)

# V0'
# NOTE : the implementation difference on cur VS self.cur
# 1) if cur : we need to ssign output of help() func to cur
# 2) if self.cur : no need to assign, plz check V0 as reference
class Solution(object):
    def convertBST(self, root):
        def help(cur, root):
            if not root:
                ### NOTE : if not root, still need to return cur
                return cur
            ### NOTE : need to assign output of help() func to cur
            cur = help(cur, root.right)
            cur += root.val
            root.val = cur
            ### NOTE : need to assign output of help() func to cur
            cur = help(cur, root.left)
            ### NOTE : need to return cur
            return cur

        if not root:
            return

        cur = 0
        help(cur, root)
        return root

# LC 200 Number of Islands, check LC 694, 711 as well
# V0 
# IDEA : DFS
class Solution(object):
    def numIslands(self, grid):
        def dfs(grid, item):
            if grid[item[0]][item[1]] == "0":
                return

            ### NOTE : MAKE grid[item[0]][item[1]] = 0 -> avoid visit again
            grid[item[0]][item[1]] = 0
            moves = [(0,1),(0,-1),(1,0),(-1,0)]
            for move in moves:
                _x = item[0] + move[0]
                _y = item[1] + move[1]
                ### NOTE : the boundary
                #       -> _x < l, _y < w
                if 0 <= _x < l and 0 <= _y < w and grid[_x][_y] != 0:
                    dfs(grid, [_x, _y])
  
        if not grid:
            return 0
        res = 0
        l = len(grid)
        w = len(grid[0])
        for i in range(l):
            for j in range(w):
                if grid[i][j] == "1":
                    ### NOTE : we go through every "1" in grids, and run dfs once
                    #         -> once dfs completed, we make res += 1 in each iteration
                    dfs(grid, [i,j])
                    res += 1
        return res

# LC 695. Max Area of Island
# V1
# https://blog.csdn.net/fuxuemingzhu/article/details/79182435
# IDEA : DFS 
# * PLEASE NOTE THAT IT IS NEEDED TO GO THROUGH EVERY ELEMENT IN THE GRID 
#   AND RUN THE DFS WITH IN THIS PROBLEM
class Solution(object):
    def maxAreaOfIsland(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        self.res = 0
        self.island = 0
        M, N = len(grid), len(grid[0])
        for i in range(M):
            for j in range(N):
                if grid[i][j]:
                    self.dfs(grid, i, j)
                    self.res = max(self.res, self.island)
                    self.island = 0
        return self.res
    
    def dfs(self, grid, i, j): # ensure grid[i][j] == 1
        M, N = len(grid), len(grid[0])
        grid[i][j] = 0
        self.island += 1
        dirs = [(0, 1), (0, -1), (-1, 0), (1, 0)]
        for d in dirs:
            x, y = i + d[0], j + d[1]
            if 0 <= x < M and 0 <= y < N and grid[x][y]:
                self.dfs(grid, x, y)

# LC 257. Binary Tree Paths
# V0 
# IDEA : DFS 
class Solution:
    # @param {TreeNode} root
    # @return {string[]}
    def binaryTreePaths(self, root):
        res, path_list = [], []
        self.dfs(root, path_list, res)
        return res

    def dfs(self, root, path_list, res):
        if not root:
            return
        path_list.append(str(root.val))
        if not root.left and not root.right:
            res.append('->'.join(path_list))
        if root.left:
            self.dfs(root.left, path_list, res)
        if root.right:
            self.dfs(root.right, path_list, res)
        path_list.pop()

# LC 236 Lowest Common Ancestor of a Binary Tree
# V0
# IDEA : RECURSION + POST ORDER TRANSVERSAL
class Solution(object):
    def lowestCommonAncestor(self, root, p, q):

        ### NOTE here
        # if not root or find p in tree or find q in tree
        # -> then we quit the recursion and return root

        ### NOTE : we compare `p == root` and  `q == root`
        if not root or p == root or q == root:
            return root
        ### NOTE here
        #  -> not root.left, root.right, BUT left, right
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        ### NOTE here
        # find q and p on the same time -> LCA is the current node (root)
        # if left and right -> p, q MUST in left, right sub tree respectively

        ### NOTE : if left and right, means this root is OK for next recursive
        if left and right:
            return root
        ### NOTE here
        # if p, q both in left sub tree or both in right sub tree
        return left if left else right

# LC 112 Path Sum
# V0
# IDEA : DFS 
class Solution(object):
    def hasPathSum(self, root, sum):
        if not root:
            return False
        if not root.left and not root.right:
            return True if sum == root.val else False
        else:
            return self.hasPathSum(root.left, sum-root.val) or self.hasPathSum(root.right, sum-root.val)

# LC 113 Path Sum II
# V0
# IDEA : DFS
class Solution(object):
    def pathSum(self, root, sum):
        if not root: return []
        res = []
        self.dfs(root, sum, res, [root.val])
        return res

    def dfs(self, root, target, res, path):
        if not root: return
        if sum(path) == target and not root.left and not root.right:
            res.append(path)
            return
        if root.left:
            self.dfs(root.left, target, res, path + [root.left.val])
        if root.right:
            self.dfs(root.right, target, res, path + [root.right.val])

// java
// LC 113
// V0
// IDEA : DFS + backtracking
// NOTE !!! we have res attr, so can use this.res collect result
private List<List<Integer>> res = new ArrayList<>();

public List<List<Integer>> pathSum(TreeNode root, int targetSum) {

    if (root == null){
        return this.res;
    }

    List<Integer> cur = new ArrayList<>();
    getPath(root, cur, targetSum);
    return this.res;
}

 private void getPath(TreeNode root, List<Integer> cur, int targetSum){

    // return directly if root is null (not possible to go further, so just quit directly)
    if (root == null){
        return;
    }

    // NOTE !!! we add val to cache here instead of while calling method recursively ( e.g. getPath(root.left, cur, targetSum - root.val))
    //          -> so we just need to backtrack (cancel last operation) once (e.g. cur.remove(cur.size() - 1);)
    //          -> please check V0' for example with backtrack in recursively step
    cur.add(root.val);

    if (root.left == null && root.right == null && targetSum == root.val){
        this.res.add(new ArrayList<>(cur));
    }else{
        // NOTE !!! we update targetSum here (e.g. targetSum - root.val)
        getPath(root.left, cur, targetSum - root.val);
        getPath(root.right, cur, targetSum - root.val);
    }

     // NOTE !!! we do backtrack here (cancel previous adding to cur)
     cur.remove(cur.size() - 1);
}

# 133 Clone graph
# note : there is also a BFS solution
# V0
# IDEA : DFS
# NOTE :
#  -> 1) we init node via : node_copy = Node(node.val, [])
#  -> 2) we copy graph via dict
class Solution(object):
    def cloneGraph(self, node):
        """
        :type node: Node
        :rtype: Node
        """
        node_copy = self.dfs(node, dict())
        return node_copy
    
    def dfs(self, node, hashd):
        if not node: return None
        if node in hashd: return hashd[node]
        node_copy = Node(node.val, [])
        hashd[node] = node_copy
        for n in node.neighbors:
            n_copy = self.dfs(n, hashd)
            if n_copy:
                node_copy.neighbors.append(n_copy)
        return node_copy

# LC 737. Sentence Similarity II
# NOTE : there is also union-find solution
# V0
# IDEA : DFS
from collections import defaultdict
class Solution(object):
    def areSentencesSimilarTwo(self, sentence1, sentence2, similarPairs):
        # helper func
        def dfs(w1, w2, visited):
            for j in d[w2]:
                if w1 == w2:
                    return True
                elif j not in visited:
                    visited.add(j)
                    if dfs(w1, j, visited):
                        return True
            return False
        
        # edge case
        if len(sentence1) != len(sentence2):
            return False
      
        d = defaultdict(list)
        for a, b in similarPairs:
            d[a].append(b)
            d[b].append(a)
            
        for i in range(len(sentence1)):
            visited =  set([sentence2[i]])
            if sentence1[i] != sentence2[i] and not dfs(sentence1[i],  sentence2[i], visited):
                return False
        return True

# clean reference (explicit graph + DFS reachability)
def areSentencesSimilarTwo(s1, s2, pairs):
    if len(s1) != len(s2):
        return False
    g = collections.defaultdict(set)
    for a, b in pairs:
        g[a].add(b); g[b].add(a)

    def connected(src, dst):
        if src == dst:
            return True
        stack, seen = [src], {src}          # seed seen w/ src to avoid re-visit
        while stack:
            w = stack.pop()
            if w == dst:
                return True
            for nei in g[w]:
                if nei not in seen:
                    seen.add(nei); stack.append(nei)
        return False

    return all(connected(a, b) for a, b in zip(s1, s2))

3 interchangeable engines (same idea, different machinery):
  DFS / BFS   -> per-query graph traversal      | O((V+E)) per query
  Union-Find  -> union all pairs, then find()    | ~O(α(n)) per query  <- best for many queries
Don't forget: w1 == w2 short-circuits TRUE even if the word isn't in the graph.

helper(A)  visited={A}        for nei in [B, C]:  -> loop PAUSES at B
 └─ helper(B)  visited={A,B}  for nei in [D]:
     └─ helper(D)  no neighbors -> return False   ── returns to helper(B) ONLY
    back in helper(B): `if False: return True` skipped; no more neighbors -> return False
back in helper(A): B branch failed, loop RESUMES -> nei = C
 └─ helper(C)  visited={A,B,D,C}  for nei in [E]:
     └─ helper(E)  E == target -> return True
    back in helper(C): `if True: return True`     -> helper(C) returns True
back in helper(A): `if True: return True`         -> helper(A) returns True

            helper(A) ───────────────► True
            ├─ helper(B) ──► False        (dead branch, did NOT stop search)
            │   └─ helper(D) ──► False
            └─ helper(C) ──► True
                └─ helper(E) ──► True

# LC 472. Concatenated Words
# V1
# http://bookshadow.com/weblog/2016/12/18/leetcode-concatenated-words/
# IDEA : DFS 
class Solution(object):
    def findAllConcatenatedWordsInADict(self, words):
        """
        :type words: List[str]
        :rtype: List[str]
        """
        ans = []
        self.wordSet = set(words)
        for word in words:
            self.wordSet.remove(word) # avoid the search process find itself (word) when search all word in words  
            if self.search(word):
                ans.append(word)
            self.wordSet.add(word)    # add the word back for next search with new "word"
        return ans

    def search(self, word):
        if word in self.wordSet:
            return True
        for idx in range(1, len(word)):
            if word[:idx] in self.wordSet and self.search(word[idx:]):
                return True
        return False

# LC 1339. Maximum Product of Splitted Binary Tree
# V0
# IDEA : DFS
class Solution(object):
    def maxProduct(self, root):
        all_sums = []

        def tree_sum(subroot):
            if subroot is None: return 0
            left_sum = tree_sum(subroot.left)
            right_sum = tree_sum(subroot.right)
            total_sum = left_sum + right_sum + subroot.val
            all_sums.append(total_sum)
            return total_sum

        total = tree_sum(root)
        best = 0
        for s in all_sums:
            best = max(best, s * (total - s))   
        return best % (10 ** 9 + 7)

# LC 297. Serialize and Deserialize Binary Tree
# V0
# IDRA : DFS
class Codec:

    def serialize(self, root):
        """ Encodes a tree to a single string.
        :type root: TreeNode
        :rtype: str
        """
        def rserialize(root, string):
            """ a recursive helper function for the serialize() function."""
            # check base case
            if root is None:
                string += 'None,'
            else:
                string += str(root.val) + ','
                string = rserialize(root.left, string)
                string = rserialize(root.right, string)
            return string
        
        return rserialize(root, '')    

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        :type data: str
        :rtype: TreeNode
        """
        def rdeserialize(l):
            """ a recursive helper function for deserialization."""
            if l[0] == 'None':
                l.pop(0)
                return None
                
            root = TreeNode(l[0])
            l.pop(0)
            root.left = rdeserialize(l)
            root.right = rdeserialize(l)
            return root

        data_list = data.split(',')
        root = rdeserialize(data_list)
        return root

# V1
# IDEA : same as LC 297
# https://leetcode.com/problems/serialize-and-deserialize-bst/discuss/93283/Python-solution-using-BST-property
class Codec:

    def serialize(self, root):
        vals = []
        self._preorder(root, vals)
        return ','.join(vals)
        
    def _preorder(self, node, vals):
        if node:
            vals.append(str(node.val))
            self._preorder(node.left, vals)
            self._preorder(node.right, vals)
        
    def deserialize(self, data):
        vals = collections.deque(map(int, data.split(','))) if data else []
        return self._build(vals, -float('inf'), float('inf'))

    def _build(self, vals, minVal, maxVal):
        if vals and minVal < vals[0] < maxVal:
            val = vals.popleft()
            root = TreeNode(val)
            root.left = self._build(vals, minVal, val)
            root.right = self._build(vals, val, maxVal)
            return root
        else:
            return None

# LC 449. Serialize and Deserialize BST
# V0
# IDEA : BFS + queue op
class Codec:
    def serialize(self, root):
        if not root:
            return '{}'

        res = [root.val]
        q = [root]

        while q:
            new_q = []
            for i in range(len(q)):
                tmp = q.pop(0)
                if tmp.left:
                    q.append(tmp.left)
                    res.extend( [tmp.left.val] )
                else:
                    res.append('#')
                if tmp.right:
                    q.append(tmp.right)
                    res.extend( [tmp.right.val] )
                else:
                    res.append('#')

        while res and res[-1] == '#':
                    res.pop()

        return '{' + ','.join(map(str, res)) + '}' 


    def deserialize(self, data):
        if data == '{}':
            return

        nodes = [ TreeNode(x) for x in data[1:-1].split(",") ]
        root = nodes.pop(0)
        p = [root]
        while p:
            new_p = []
            for n in p:
                if nodes:
                    left_node = nodes.pop(0)
                    if left_node.val != '#':
                        n.left = left_node
                        new_p.append(n.left)
                    else:
                        n.left = None
                if nodes:
                    right_node = nodes.pop(0)
                    if right_node.val != '#':
                        n.right = right_node
                        new_p.append(n.right)
                    else:
                        n.right = None
            p = new_p 
             
        return root

# V1
# IDEA : same as LC 297
# https://leetcode.com/problems/serialize-and-deserialize-bst/discuss/93283/Python-solution-using-BST-property
class Codec:

    def serialize(self, root):
        vals = []
        self._preorder(root, vals)
        return ','.join(vals)
        
    def _preorder(self, node, vals):
        if node:
            vals.append(str(node.val))
            self._preorder(node.left, vals)
            self._preorder(node.right, vals)
        
    def deserialize(self, data):
        vals = collections.deque(map(int, data.split(','))) if data else []
        return self._build(vals, -float('inf'), float('inf'))

    def _build(self, vals, minVal, maxVal):
        if vals and minVal < vals[0] < maxVal:
            val = vals.popleft()
            root = TreeNode(val)
            root.left = self._build(vals, minVal, val)
            root.right = self._build(vals, val, maxVal)
            return root
        else:
            return None

// java
// LC 1254
// V0
// IDEA: 2-Pass DFS (Boundary Elimination)
/**
 * Algorithm:
 * Pass 1: Start from all boundary cells and flood-fill to eliminate
 *         all islands connected to the boundary (these cannot be closed)
 * Pass 2: Count remaining land cells as closed islands
 *
 * Time: O(m×n), Space: O(m×n) for recursion stack
 */
public int closedIsland(int[][] grid) {
    if (grid == null || grid.length == 0) {
        return 0;
    }

    int rows = grid.length;
    int cols = grid[0].length;

    // Pass 1: Eliminate boundary-connected islands
    // Flood top and bottom borders
    for (int c = 0; c < cols; c++) {
        flood(grid, 0, c);           // Top border
        flood(grid, rows - 1, c);    // Bottom border
    }

    // Flood left and right borders
    for (int r = 0; r < rows; r++) {
        flood(grid, r, 0);           // Left border
        flood(grid, r, cols - 1);    // Right border
    }

    // Pass 2: Count closed islands
    int count = 0;
    for (int r = 1; r < rows - 1; r++) {
        for (int c = 1; c < cols - 1; c++) {
            if (grid[r][c] == 0) {
                count++;
                flood(grid, r, c);  // Mark entire island
            }
        }
    }

    return count;
}

private void flood(int[][] grid, int r, int c) {
    int rows = grid.length;
    int cols = grid[0].length;

    // Base case: out of bounds or water
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] == 1) {
        return;
    }

    grid[r][c] = 1;  // Mark land as water (visited)

    // Flood 4-directionally
    flood(grid, r + 1, c);
    flood(grid, r - 1, c);
    flood(grid, r, c + 1);
    flood(grid, r, c - 1);
}

# python
# LC 1254
def closedIsland(grid):
    """
    2-Pass DFS approach
    """
    if not grid or not grid[0]:
        return 0

    rows, cols = len(grid), len(grid[0])

    def flood(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == 1:
            return
        grid[r][c] = 1
        flood(r + 1, c)
        flood(r - 1, c)
        flood(r, c + 1)
        flood(r, c - 1)

    # Pass 1: Eliminate boundary islands
    for c in range(cols):
        flood(0, c)
        flood(rows - 1, c)

    for r in range(rows):
        flood(r, 0)
        flood(r, cols - 1)

    # Pass 2: Count closed islands
    count = 0
    for r in range(1, rows - 1):
        for c in range(1, cols - 1):
            if grid[r][c] == 0:
                count += 1
                flood(r, c)

    return count

// java
// LC 417
// V0
// IDEA : DFS (fixed by GPT)

public List<List<Integer>> pacificAtlantic(int[][] heights) {

    if (heights == null || heights.length == 0 || heights[0].length == 0) {
        return new ArrayList<>();
    }

    int l = heights.length;
    int w = heights[0].length;

    /**
     *
     * The pacificReachable and atlanticReachable arrays are used to keep track
     * of which cells in the matrix can reach the Pacific and Atlantic oceans, respectively.
     *
     *
     * - pacificReachable[i][j] will be true if water
     *   can flow from cell (i, j) to the Pacific Ocean.
     *   The Pacific Ocean is on the top and left edges of the matrix.
     *
     * - atlanticReachable[i][j] will be true if water
     *   can flow from cell (i, j) to the Atlantic Ocean.
     *   The Atlantic Ocean is on the bottom and right edges of the matrix.
     *
     *
     * NOTE !!!!
     *
     * The pacificReachable and atlanticReachable arrays serve a dual purpose:
     *
     * Tracking Reachability: They track whether each cell can reach the respective ocean.
     *
     * Tracking Visited Cells: They also help in tracking whether a cell has already
     *                         been visited during the depth-first search (DFS)
     *                         to prevent redundant work and infinite loops.
     *
     *
     *   NOTE !!!
     *
     *    we use `boolean[][]` to track if a cell is reachable
     */
    boolean[][] pacificReachable = new boolean[l][w];
    boolean[][] atlanticReachable = new boolean[l][w];

    // check on x-axis
    /**
     *  NOTE !!!
     *
     *   we loop EVERY `cell` at x-axis  ( (x_1, 0), (x_2, 0), .... (x_1, l - 1), (x_2, l - 1) ... )
     *
     */
    for (int x = 0; x < w; x++) {
        dfs(heights, pacificReachable, 0, x);
        dfs(heights, atlanticReachable, l - 1, x);
    }

    // check on y-axis
    /**
     *  NOTE !!!
     *
     *   we loop EVERY `cell` at y-axis  (  (0, y_1), (0, y_2), .... (w-1, y_1), (w-1, y_2), ... )
     *
     */
    for (int y = 0; y < l; y++) {
        dfs(heights, pacificReachable, y, 0);
        dfs(heights, atlanticReachable, y, w - 1);
    }

    List<List<Integer>> commonCells = new ArrayList<>();
    for (int i = 0; i < l; i++) {
        for (int j = 0; j < w; j++) {
            if (pacificReachable[i][j] && atlanticReachable[i][j]) {
                commonCells.add(Arrays.asList(i, j));
            }
        }
    }
    return commonCells;
}

/**
 *  NOTE !!!
 *
 *   this dfs func return NOTHING,
 *   e.g. it updates the matrix value `in place`
 *
 *   example:  we pass `pacificReachable` as param to dfs,
 *             it modifies values in pacificReachable in place,
 *             but NOT return pacificReachable as response
 */
private void dfs(int[][] heights, boolean[][] reachable, int y, int x) {

    int l = heights.length;
    int w = heights[0].length;

    reachable[y][x] = true;

    int[][] directions = new int[][]{{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
    for (int[] dir : directions) {
        int newY = y + dir[0];
        int newX = x + dir[1];

        /**
         *  NOTE !!!  only meet below conditions, then do recursion call
         *
         *  1. newX, newY still in range
         *  2. newX, newY is still not reachable (!reachable[newY][newX])
         *  3. heights[newY][newX] >= heights[y][x]
         *
         *
         *  NOTE !!!
         *
         *  The condition !reachable[newY][newX] in the dfs function
         *  ensures that each cell is only processed once
         *
         *  1. Avoid Infinite Loops
         *  2. Efficiency
         *  3. Correctness
         *
         *
         *  NOTE !!! "inverse" comparison
         *
         *  we use the "inverse" comparison, e.g.  heights[newY][newX] >= heights[y][x]
         *  so we start from "cur point" (heights[y][x]), and compare with "next point" (heights[newY][newX])
         *  if "next point" is "higher" than "cur point"  (e.g. heights[newY][newX] >= heights[y][x])
         *  -> then means water at "next point" can flow to "cur point"
         *  -> then we keep track back to next point of then "next point"
         *  -> repeat ...
         */
        if (newY >= 0 && newY < l && newX >= 0 && newX < w && !reachable[newY][newX] && heights[newY][newX] >= heights[y][x]) {
            dfs(heights, reachable, newY, newX);
        }
    }
} 

// java
// LC 529

// (there is also BFS solution)

// V1
// IDEA: DFS + ARRAY OP (GPT)
public char[][] updateBoard_1(char[][] board, int[] click) {
    int rows = board.length;
    int cols = board[0].length;

    int x = click[0], y = click[1];

    // Edge case: 1x1 grid
    if (rows == 1 && cols == 1) {
        if (board[0][0] == 'M') {
            board[0][0] = 'X';
        } else {
            board[0][0] = 'B'; // Fix: properly set 'B' if it's 'E'
        }
        return board;
    }

    // If a mine is clicked, mark as 'X'
    if (board[x][y] == 'M') {
        board[x][y] = 'X';
        return board;
    }

    // Otherwise, reveal cells recursively
    reveal_1(board, x, y);
    return board;
}

private void reveal_1(char[][] board, int x, int y) {
    int rows = board.length;
    int cols = board[0].length;

// Boundary check and already revealed check
/** NOTE !!!
 *
 *  - 1) 'E' represents an unrevealed empty square,
 *
 *  - 2) board[x][y] != 'E'
 *      -> ensures that we only process unrevealed empty cells ('E')
 *         and avoid unnecessary recursion.
 *
 *   - 3) board[x][y] != 'E'
 *   •  Avoids re-processing non-‘E’ cells
 *   •  The board can have:
 *      •   'M' → Mine (already handled separately)
 *      •   'X' → Clicked mine (game over case)
 *      •   'B' → Blank (already processed)
 *      •   '1' to '8' → Number (already processed)
 *  •   If a cell is not 'E', it means:
 *      •   It has already been processed
 *      •   It does not need further expansion
 *  •   This prevents infinite loops and redundant checks.
 *
 *
 *  - 4) example:
 *
 *     input:
 *          E E E
 *          E M E
 *          E E E
 *
 *   Click at (0,0)
 *      1.  We call reveal(board, 0, 0), which:
 *          •   Counts 1 mine nearby → Updates board[0][0] = '1'
 *          •   Does NOT recurse further, avoiding unnecessary work.
 *
 *      What If We Didn’t Check board[x][y] != 'E'?
 *          •   It might try to expand into already processed cells, leading to redundant computations or infinite recursion.
 *
 */
if (x < 0 || x >= rows || y < 0 || y >= cols || board[x][y] != 'E') {
        return;
    }

    // Directions for 8 neighbors
    int[][] directions = {
            { -1, -1 }, { -1, 0 }, { -1, 1 },
            { 0, -1 }, { 0, 1 },
            { 1, -1 }, { 1, 0 }, { 1, 1 }
    };

    // Count adjacent mines
    int mineCount = 0;
    for (int[] dir : directions) {
        int newX = x + dir[0];
        int newY = y + dir[1];
        if (newX >= 0 && newX < rows && newY >= 0 && newY < cols && board[newX][newY] == 'M') {
            mineCount++;
        }
    }

    // If there are adjacent mines, show count
    if (mineCount > 0) {
        board[x][y] = (char) ('0' + mineCount);
    } else {
        // Otherwise, reveal this cell and recurse on neighbors
        board[x][y] = 'B';
        for (int[] dir : directions) {
            reveal_1(board, x + dir[0], y + dir[1]);
        }
    }
}

// java
// LC 3319

// V0-1
// IDEA: DFS (fixed by gpt)
//  Time Complexity: O(N log N)
//  Space Complexity: O(N)
/**
*  Objective recap:
*
*   We want to:
*    •   Find all perfect binary subtrees in the given tree.
*    •   A perfect binary tree is one where:
*        •   Every node has 0 or 2 children (i.e., full),
*        •   All leaf nodes are at the `same depth`.
*    •   Return the k-th largest size among these perfect subtrees.
*    •   If there are fewer than k perfect subtrees, return -1.
*
*/
// This is a class-level list that stores the sizes of all perfect subtrees we discover during traversal.
List<Integer> perfectSizes = new ArrayList<>();

public int kthLargestPerfectSubtree_0_1(TreeNode root, int k) {
    dfs(root);
    if (perfectSizes.size() < k)
        return -1;

    Collections.sort(perfectSizes, Collections.reverseOrder());
    return perfectSizes.get(k - 1);
}

// Helper class to store information about each subtree
/**
*
* It returns a helper object SubtreeInfo, which contains:
*    •   height: depth of the subtree rooted at node.
*    •   size: number of nodes in the subtree.
*    •   isPerfect: boolean indicating whether this subtree is perfect.
*
*/
private static class SubtreeInfo {
    int height;
    int size;
    boolean isPerfect;

    SubtreeInfo(int height, int size, boolean isPerfect) {
        this.height = height;
        this.size = size;
        this.isPerfect = isPerfect;
    }
}

/**
* Inside dfs():
*    1.  Base case:
*        •   If node == null, we return a SubtreeInfo with height 0, size 0, and isPerfect = true.
*    2.  Recurse on left and right children.
*    3.  Check if the subtree rooted at this node is perfect:
*
*/
private SubtreeInfo dfs(TreeNode node) {
    if (node == null) {
        return new SubtreeInfo(0, 0, true);
    }

    SubtreeInfo left = dfs(node.left);
    SubtreeInfo right = dfs(node.right);

/**  NOTE !!!  below logic:
 *
 * This ensures:
 *  •   Both left and right subtrees are perfect.
 *  •   Their `heights` are the same → leaves are at the `same level`.
 */
boolean isPerfect = left.isPerfect && right.isPerfect
        && (left.height == right.height);


    int size = left.size + right.size + 1;
    int height = Math.max(left.height, right.height) + 1;

    /**
     *  NOTE !!!
     *
     *  If the current subtree is perfect, we record its size:
     *
     */
    if (isPerfect) {
        perfectSizes.add(size);
    }

    return new SubtreeInfo(height, size, isPerfect);
}

DFS Problem Analysis Flowchart:

1. Is it a tree/graph traversal problem?
   ├── YES → Check structure type
   │   ├── Tree? → Use Tree Templates (1, 3, 5, 6)
   │   │   ├── Need specific order? → Template 1 (Traversal)
   │   │   ├── Need paths? → Template 3 (Path Finding)
   │   │   ├── Need to modify? → Template 5 (Modification)
   │   │   └── Need subtree info? → Template 6 (Bottom-up)
   │   └── Graph? → Use Graph Template (2)
   │       ├── Has cycles? → Add visited set
   │       ├── Need all paths? → Track path
   │       └── Multi-source? → Start from all sources
   └── NO → Continue to 2

2. Is it a combinatorial problem?
   ├── YES → Use Backtracking Template (4)
   │   ├── Permutations? → Swap elements
   │   ├── Combinations? → Start index
   │   ├── Subsets? → Include/exclude
   │   └── Constraint satisfaction? → Check validity
   └── NO → Continue to 3

3. Does it require exploring all possibilities?
   ├── YES → Use DFS with appropriate state tracking
   │   ├── Grid problem? → 4-directional DFS
   │   ├── String problem? → Index-based DFS
   │   └── Decision tree? → Choice-based DFS
   └── NO → Consider different algorithm

4. Special considerations:
   ├── Need shortest path? → Consider BFS instead
   ├── Has optimal substructure? → Consider DP
   └── Need all solutions? → DFS with backtracking

class Solution:
    def maxPathSum(self, root):
        self.max_sum = float('-inf')
        
        def dfs(node):
            if not node:
                return 0
            left = max(0, dfs(node.left))
            right = max(0, dfs(node.right))
            self.max_sum = max(self.max_sum, left + right + node.val)
            return max(left, right) + node.val
        
        dfs(root)
        return self.max_sum

def all_paths(root):
    result = []
    
    def dfs(node, path):
        if not node:
            return
        
        path.append(node.val)  # Make choice
        
        if not node.left and not node.right:
            result.append(path[:])  # Found complete path
        
        dfs(node.left, path)
        dfs(node.right, path)
        
        path.pop()  # Unmake choice (backtrack)
    
    dfs(root, [])
    return result

def grid_dfs(grid, x, y, visited):
    if x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0]):
        return
    if (x, y) in visited or grid[x][y] == 0:
        return
    
    visited.add((x, y))
    
    # 4-directional movement
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    for dx, dy in directions:
        grid_dfs(grid, x + dx, y + dy, visited)

private boolean dfsPathVisitor(int node, int destination, Map<Integer, List<Integer>> map, boolean[] visited) {
    if (node == destination) return true;

    visited[node] = true;

    for (int next : map.get(node)) {
        if (!visited[next]) {
            // ❌ WRONG: Ignoring return value - continues searching even after path found!
            dfsPathVisitor(next, destination, map, visited);
        }
    }

    return false;  // Will ALWAYS return false (except for direct hits)
}

private boolean dfsPathVisitor(int node, int destination, Map<Integer, List<Integer>> map, boolean[] visited) {
    if (node == destination) return true;

    visited[node] = true;

    for (int next : map.get(node)) {
        if (!visited[next]) {
            // ✅ CORRECT: Return immediately when path found!
            if (dfsPathVisitor(next, destination, map, visited)) {
                return true;
            }
        }
    }

    return false;  // Only return false if ALL paths explored
}

Graph: 0 -- 1 -- 2 -- 3
       |         |
       4 -------- 5

Adjacency List:
0: [1, 4]
1: [0, 2]
2: [1, 3, 5]
3: [2]
4: [0, 5]
5: [2, 4]

Task: Find path from 0 to 3

1. dfsPathVisitor(0, 3, ..., visited=[])
   → visited = [0]
   → Loop neighbors: [1, 4]

   2. dfsPathVisitor(1, 3, ..., visited=[0])  // First neighbor
      → visited = [0, 1]
      → Loop neighbors: [0, 2]  (skip 0, already visited)

      3. dfsPathVisitor(2, 3, ..., visited=[0,1])
         → visited = [0, 1, 2]
         → Loop neighbors: [1, 3, 5]  (skip 1)

         4. dfsPathVisitor(3, 3, ..., visited=[0,1,2])
            → ✅ Found! Returns TRUE

         ← Returns TRUE to level 3

      ← But level 2 IGNORES the return value!
      ← Continues checking neighbor 5

      5. dfsPathVisitor(5, 3, ..., visited=[0,1,2])
         → visited = [0, 1, 2, 5]
         → Loop neighbors: [2, 4]  (both visited)
         ← Returns FALSE

      ← Level 2 finishes loop, returns FALSE

   ← Level 1 receives FALSE from neighbor 1

   6. dfsPathVisitor(4, 3, ..., visited=[0,1,2,5])  // Second neighbor
      → visited = [0, 1, 2, 5, 4]
      → Loop neighbors: [0, 5]  (both visited)
      ← Returns FALSE

   ← Level 0 finishes loop, returns FALSE

❌ FINAL RESULT: FALSE (Path exists but not detected!)

1. dfsPathVisitor(0, 3, ..., visited=[])
   → visited = [0]
   → Loop neighbors: [1, 4]

   2. dfsPathVisitor(1, 3, ..., visited=[0])  // First neighbor
      → visited = [0, 1]
      → Loop neighbors: [0, 2]  (skip 0)

      3. dfsPathVisitor(2, 3, ..., visited=[0,1])
         → visited = [0, 1, 2]
         → Loop neighbors: [1, 3, 5]  (skip 1)

         4. dfsPathVisitor(3, 3, ..., visited=[0,1,2])
            → ✅ Found! Returns TRUE

         ← Returns TRUE to level 3

      ← Level 2 checks: if (TRUE) return true;  ✅
      ← Returns TRUE immediately (skips remaining neighbors!)

   ← Level 1 checks: if (TRUE) return true;  ✅
   ← Returns TRUE immediately (skips neighbor 4!)

✅ FINAL RESULT: TRUE (Correct!)

// Use when: "Does path exist?" "Can we reach?" "Is there a route?"
if (dfs(next)) {
    return true;  // Found one path - that's enough!
}

// Use when: "Find ALL paths" "Count all solutions" "Collect all combinations"
dfs(next);  // Don't return early - need to explore all branches

private boolean dfsPathVisitor(int node, int destination,
                                Map<Integer, List<Integer>> map,
                                boolean[] visited) {
    // Base case: destination reached
    if (node == destination)
        return true;

    // Mark current node as visited
    visited[node] = true;

    // Visit neighbors
    for (int next : map.get(node)) {
        if (!visited[next]) {
            // ✅ CRITICAL: Check return value and return immediately if path found
            if (dfsPathVisitor(next, destination, map, visited)) {
                return true;
            }

            // ❌ WRONG PATTERN (commented out):
            // if (!dfsPathVisitor(next, destination, map, visited)) {
            //     return false;  // This would fail for graphs with multiple paths!
            // }
        }
    }

    return false;  // Only return false if ALL neighbors failed
}

// java
// LC 694
// V0
// IDEA: DFS + Path Signatures (Directional Encoding)
/**
 * Problem: Count distinct island shapes (translation-invariant)
 *
 * Key Insight: Two islands are the same if one can be translated (NOT rotated/reflected) to match the other
 *
 * Solution Approach:
 * 1. For each island, generate a unique "path signature" encoding its shape
 * 2. Use a HashSet to count distinct signatures
 * 3. Signature must be translation-invariant but rotation/reflection-sensitive
 *
 * Critical Implementation Details:
 * - Canonical traversal order (always D, U, R, L)
 * - Starting point normalization (top-left via grid iteration order)
 * - Backtracking delimiter ('O') to distinguish shapes
 */
public int numDistinctIslands(int[][] grid) {
    if (grid == null || grid.length == 0 || grid[0].length == 0) {
        return 0;
    }

    Set<String> uniqueIslandShapes = new HashSet<>();
    int rows = grid.length;
    int cols = grid[0].length;

    // Iterate through grid in fixed order (top-to-bottom, left-to-right)
    // This ensures the starting point for each island is always the top-left-most cell
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            // Start DFS only on unvisited land cells
            if (grid[r][c] == 1) {
                StringBuilder pathSignature = new StringBuilder();
                // 'S' marks the start position
                dfs(grid, r, c, pathSignature, 'S');

                if (pathSignature.length() > 0) {
                    uniqueIslandShapes.add(pathSignature.toString());
                }
            }
        }
    }

    return uniqueIslandShapes.size();
}

/**
 * DFS with directional encoding
 *
 * @param grid The grid, modified in-place (cells set to 0 when visited)
 * @param r Current row
 * @param c Current column
 * @param path StringBuilder to build the signature
 * @param direction Direction taken to arrive at (r, c)
 */
private void dfs(int[][] grid, int r, int c, StringBuilder path, char direction) {
    int rows = grid.length;
    int cols = grid[0].length;

    // Base Case 1: Out of bounds
    if (r < 0 || r >= rows || c < 0 || c >= cols) {
        return;
    }

    // Base Case 2: Water (0) or already visited land (already marked as 0)
    if (grid[r][c] == 0) {
        return;
    }

    // 1. Mark the current cell as visited by setting it to water (0)
    // This prevents double counting and replaces the need for a separate visited array
    grid[r][c] = 0;

    // 2. Record the direction of movement into this cell
    path.append(direction);

    // 3. Recurse into neighbors in FIXED order (critical for consistency!)
    // The order must always be the same to ensure identical islands produce identical signatures
    dfs(grid, r + 1, c, path, 'D');  // Down
    dfs(grid, r - 1, c, path, 'U');  // Up
    dfs(grid, r, c + 1, path, 'R');  // Right
    dfs(grid, r, c - 1, path, 'L');  // Left

    // 4. Crucial Step: Add an "Out" (O) delimiter when returning from this cell
    // This marks the end of a branch and distinguishes shapes that follow different paths
    // Without this, different shapes could produce the same signature!
    path.append('O');
}

// V1
// IDEA: Alternative approach using relative coordinates
/**
 * Instead of directional encoding, record relative positions from the starting point
 */
public int numDistinctIslands_v2(int[][] grid) {
    if (grid == null || grid.length == 0) return 0;
    int rows = grid.length, cols = grid[0].length;
    boolean[][] seen = new boolean[rows][cols];
    Set<String> shapes = new HashSet<>();

    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (!seen[r][c] && grid[r][c] == 1) {
                StringBuilder sb = new StringBuilder();
                // Pass starting coordinates (r, c) as origin
                dfsRelative(grid, seen, r, c, r, c, sb);
                shapes.add(sb.toString());
            }
        }
    }
    return shapes.size();
}

/**
 * DFS that records relative coordinates from origin (r0, c0)
 */
private void dfsRelative(int[][] grid, boolean[][] seen, int r0, int c0, int r, int c, StringBuilder sb) {
    int rows = grid.length, cols = grid[0].length;
    if (r < 0 || r >= rows || c < 0 || c >= cols) return;
    if (seen[r][c] || grid[r][c] != 1) return;

    seen[r][c] = true;
    // Record relative position: (r - r0, c - c0)
    // This makes the signature translation-invariant
    sb.append((r - r0)).append('_').append((c - c0)).append(',');

    // Visit in fixed order (critical!)
    dfsRelative(grid, seen, r0, c0, r + 1, c, sb);
    dfsRelative(grid, seen, r0, c0, r - 1, c, sb);
    dfsRelative(grid, seen, r0, c0, r, c + 1, sb);
    dfsRelative(grid, seen, r0, c0, r, c - 1, sb);
}

# python
# LC 694
# V0
# IDEA: DFS + Path Signatures
def numDistinctIslands(grid):
    """
    Count distinct island shapes using directional path encoding

    Example:
    Input: grid = [[1,1,0,0,0],
                   [1,1,0,0,0],
                   [0,0,0,1,1],
                   [0,0,0,1,1]]
    Output: 1
    Explanation: Both islands have the same shape

    The path signature for both islands would be: "SDROO" or similar
    """
    if not grid or not grid[0]:
        return 0

    rows, cols = len(grid), len(grid[0])
    unique_shapes = set()

    def dfs(r, c, direction, path):
        # Out of bounds or water/visited
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != 1:
            return

        # Mark as visited
        grid[r][c] = 0

        # Record direction
        path.append(direction)

        # Visit in fixed order: Down, Up, Right, Left
        dfs(r + 1, c, 'D', path)
        dfs(r - 1, c, 'U', path)
        dfs(r, c + 1, 'R', path)
        dfs(r, c - 1, 'L', path)

        # Add backtrack delimiter
        path.append('O')

    # Process each island
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                path = []
                dfs(r, c, 'S', path)  # 'S' for start
                unique_shapes.add(tuple(path))

    return len(unique_shapes)

// Java DFS with Stack
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
    TreeNode node = stack.pop();
    // Process node
    if (node.right != null) stack.push(node.right);
    if (node.left != null) stack.push(node.left);
}

// Graph DFS with adjacency list
void dfs(int node, boolean[] visited, List<List<Integer>> adj) {
    visited[node] = true;
    for (int neighbor : adj.get(node)) {
        if (!visited[neighbor]) {
            dfs(neighbor, visited, adj);
        }
    }
}

# Using collections.deque as stack
from collections import deque
stack = deque([root])
while stack:
    node = stack.pop()  # pop() for stack behavior
    # Process node

# Graph representation
graph = defaultdict(list)  # Adjacency list
visited = set()  # Track visited nodes

# Recursion limit for deep trees
import sys
sys.setrecursionlimit(10000)

# python
# LC 990 - Satisfiability of Equality Equations
# IDEA: DFS — group `==` variables into a graph, then check `!=` contradictions
# time = O(N^2) worst case (DFS per `!=`), space = O(N)
class Solution(object):
    def equationsPossible(self, equations):
        same_group = {}

        # 1) init nodes so graph[x] never KeyErrors
        for eq in equations:
            a, b = eq[0], eq[3]
            same_group.setdefault(a, [])
            same_group.setdefault(b, [])

        # 2) build UNDIRECTED graph from `==` only (bi-directional is required!)
        for eq in equations:
            a, b = eq[0], eq[3]
            if eq[1:3] == "==":
                same_group[a].append(b)
                same_group[b].append(a)

        # 3) verify each `!=` : if a can reach b, it's a contradiction
        for eq in equations:
            a, b = eq[0], eq[3]
            if eq[1:3] == "!=":
                visited = set()
                if self.helper(a, b, same_group, visited):
                    return False
        return True

    def helper(self, cur, target, graph, visited):
        if cur == target:          # reachable → forced equal → contradiction
            return True
        if cur in visited:
            return False
        visited.add(cur)
        for nxt in graph[cur]:
            if self.helper(nxt, target, graph, visited):
                return True
        return False

# python
# LC 990 - Union-Find
class Solution:
    def equationsPossible(self, equations):
        uf = {}
        def find(x):
            uf.setdefault(x, x)
            if x != uf[x]:
                uf[x] = find(uf[x])   # path compression
            return uf[x]
        def union(x, y):
            uf[find(x)] = find(y)

        for e in equations:
            if e[1] == '=':
                union(e[0], e[-1])
        for e in equations:
            if e[1] == '!':
                if find(e[0]) == find(e[-1]):
                    return False
        return True

START: What are you trying to do with the graph/tree?
│
├─ Need to VISIT ALL NODES in specific order?
│  │
│  ├─ Yes, in preorder/inorder/postorder → Pattern 1 (Tree Traversal)
│  │                                        Examples: LC 94, 144, 145
│  │
│  └─ Yes, but need to TRY ALL COMBINATIONS → Pattern 4 (Backtracking)
│                                              Examples: LC 46, 78, 39, 17
│
├─ Working with PATHS in tree/graph?
│  │
│  ├─ Need specific path with sum/property → Pattern 2 (Path Problems)
│  │                                          Examples: LC 112, 113, 257
│  │
│  └─ Need to AGGREGATE from subtrees → Pattern 6 (Subtree Problems)
│                                        Examples: LC 508, 652, 236
│
├─ Working with GRAPH structure?
│  │
│  ├─ Need to find components/islands → Pattern 3 (Graph Traversal)
│  │                                     Examples: LC 200, 695, 133
│  │
│  ├─ Need to eliminate boundary first → Pattern 7 (Boundary Elimination)
│  │                                      Examples: LC 1254, 130, 417
│  │
│  ├─ Need to identify unique shapes → Pattern 8 (Path Signatures)
│  │                                    Examples: LC 694, 711, 652
│  │
│  ├─ Need to validate sub-components → Pattern 9 (DFS with Validation)
│  │                                     Examples: LC 1905
│  │
│  ├─ Need to count edge reversals → Pattern 10 (Bidirectional Direction Tracking)
│  │                                  Examples: LC 1466
│  │
│  └─ Need to count unreachable pairs → Pattern 11 (Component Pair Counting)
│                                        Examples: LC 2316
│
└─ Need to MODIFY tree structure?
   │
   └─ Delete/insert/trim nodes → Pattern 5 (Tree Modification)
                                  Examples: LC 450, 701, 669