Think about who starts the game and what numbers each player is allowed to subtract.

Mahmoud starts first and can subtract even numbers.

Ehab goes next and can subtract odd numbers.

Now consider what happens depending on the parity of n.

• If n is even, Mahmoud can subtract n on his first turn and leave n = 0 — Ehab can't play.
• If n is odd, Mahmoud can't subtract the entire n (since it's not even), so the game goes longer.

Regardless of the number chosen in each turn, the key idea is that the parity of n determines who makes the last move.

Since they subtract at least 1 each turn, the number of moves is exactly n. Mahmoud starts, so:

• If n is even, Mahmoud moves last.
• If n is odd, Ehab moves last.

The game lasts exactly n moves, since in each move exactly 1 is subtracted (minimum).

• If n is even: Mahmoud makes the first and last move — he wins.
• If n is odd: Ehab makes the last move — he wins.

n = int(input())
if n % 2 == 0:
    print("Mahmoud")
else:
    print("Ehab")

We are working with a grid where each non-zero region of connected cells (up/down/left/right) forms a lake. The goal is to find the maximum volume (sum of cell values) among all such lakes.

We must explore these connected components efficiently.

To explore connected components, we can use DFS or BFS. Since you asked for iterative, we'll use a stack-based DFS.

For each unvisited cell with a value > 0, we simulate DFS using a stack to explore the lake and sum its total volume.

We need to: - Keep a visited matrix to avoid reprocessing cells. - For each new starting point, push it to a stack and explore all 4-directionally connected water cells. - Update the max_volume after exploring each lake.

This guarantees each cell is visited exactly once.

Time Complexity: - O(n * m) per test case — each cell is visited at most once. - Since the sum over all test cases is ≤ 10⁶ cells, this is efficient.

Space Complexity: - O(n * m) for the visited matrix. - Up to O(n * m) for the DFS stack in the worst case (entire grid is one lake).

t = int(input())

for _ in range(t):
    n, m = map(int, input().split())
    grid = [list(map(int, input().split())) for _ in range(n)]
    visited = [[False]*m for _ in range(n)]
    
    max_volume = 0
    directions = [(-1,0), (1,0), (0,-1), (0,1)]

    for i in range(n):
        for j in range(m):
            if grid[i][j] > 0 and not visited[i][j]:
                stack = [(i, j)]
                visited[i][j] = True
                volume = 0

                while stack:
                    x, y = stack.pop()
                    volume += grid[x][y]

                    for dx, dy in directions:
                        nx, ny = x + dx, y + dy
                        if 0 <= nx < n and 0 <= ny < m:
                            if not visited[nx][ny] and grid[nx][ny] > 0:
                                visited[nx][ny] = True
                                stack.append((nx, ny))
                
                max_volume = max(max_volume, volume)
    
    print(max_volume)

Let $$$ways v$$$ array be the number of ways from which an apple can fall if it is in the vertex v. Then the answer to the query is $$$ways[v]⋅ways[u]$$$.

Note that the value of $$$ways[v]$$$ is equal to the number of leaves in the subtree of vertex $$$v$$$. Then, these values can be computed using the DFS or BFS. The value $$$ways$$$ for a vertex will be equal to 1 if this vertex is a leaf, otherwise it will be equal to the sum of these values for all children of the vertex.

Total complexity: $$$O(n+q)$$$.

from types import GeneratorType

def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc



testcase = int(input())

for _ in range(testcase):
    n = int(input())
    
    graph = [[] for _ in range(n+1)]
    

    for _ in range(n-1):
        u, v = map(int, input().split())
        graph[u].append(v)
        graph[v].append(u)
    
    ways = [0 for _ in range(n + 1)] #the number of ways each apple will fall
    
    seen = [0 for _ in range(n + 1)]
    
    @bootstrap
    def dfs(node, parent):
        
        seen[node] = 1 
        
        for nbr in graph[node]:
            if not seen[nbr]:
                yield dfs(nbr, node)
        
        #this part is done once the dfs is returning
        is_leaf = True
        for nbr in graph[node]:
            if nbr != parent:
                ways[node] += ways[nbr]
                #if node has a neighbour other than its parent 
                #it means it is not a leaf node
                is_leaf = False 
        
        #if node is a leaf node we have to set its ways to 1
        if is_leaf:
            ways[node] = 1
        
        yield
    
    dfs(1, 0) 
    
    
    q = int(input())

    # now for each pair a b we just return ways of a * ways of b
    for _ in range(q):
        a, b = map(int, input().split())
        
        print(ways[a] * ways[b])

testcase = int(input())

for _ in range(testcase):
    n = int(input())
    
    graph = [[] for _ in range(n+1)]
    
    for _ in range(n-1):
        u, v = map(int, input().split())
        graph[u].append(v)
        graph[v].append(u)
    
    ways = [0 for _ in range(n + 1)] #the number of ways each apple will fall
    
    
    
    
    def dfs(root):
        # The stack is holding (node, parent, state)
        # state means are we returning to the node or is it the first time we visit it 
        stack = [(root, 0, 0)]  # since the root node has no parent  
        seen = [0 for _ in range(n + 1)]
        
        # here we mark whatever is in the stack as seen so . . .
        seen[root] = 1 
        
        while stack:
            node, parent, state = stack.pop()
            
            if state == 1:
                # This means we are returning from a call 
                
                is_leaf = True
                
                for nbr in graph[node]:
                    if nbr != parent:
                        is_leaf = False
                        ways[node] += ways[nbr]
                
                if is_leaf:
                    ways[node] = 1 
                        
        
                # WE HAVE TO CONTINUE SINCE WE DO NOT WANT TO RE APPEND 
                continue 
            
            stack.append((node, parent, 1))
            
            for nbr in graph[node]:
                if not seen[nbr]:
                    stack.append((nbr, node, 0)) # append with state 0 since this is the first time we visit it
                    seen[nbr] = 1
            
    
    dfs(1)
    
    
    
    
    q = int(input())

    # now for each pair a b we just return ways of a * ways of b
    for _ in range(q):
        a, b = map(int, input().split())
        
        print(ways[a] * ways[b])

                           

How do we find all lakes with their corresponding indices?

Which part of the lakes should we change to land?

We need exactly k lakes to remain on the grid. A lake is a group of water cells (.) connected by sides that do not touch the border. Any water body connected to the border is considered part of the ocean and must be ignored.

DFS IS OFTEN USED TO FIND CONNECTED COMPONENTS IN A GRID. THAT's ONE APPLICATION WE'VE SEEN.

We use DFS to explore each unvisited water cell and gather its size and positions. If any part of the component touches the border, we discard it; otherwise, we store it as a valid lake.

After collecting all valid lakes, we sort them by size and fill the smallest (total_lakes — k) by turning their . cells into *. This ensures we preserve the largest lakes while making the minimum number of changes.

We then print the number of modified cells and the updated grid.

import sys
import threading

def solve():
    n, m, k = map(int, input().split())
    grid = [input() for _ in range(n)]

    def is_border(x, y):
        return x == 0 or y == 0 or x == n - 1 or y == m - 1

    def in_bounds(x, y):
        return 0 <= x < n and 0 <= y < m

    def dfs(x, y):
        vis.add((x, y))
        nonlocal size, is_lake, lake_cells
        lake_cells.add((x, y))
        if is_border(x, y):
            is_lake = False
        size += 1

        for dx, dy in dirs:
            nx, ny = x + dx, y + dy
            if in_bounds(nx, ny) and (nx, ny) not in vis and grid[nx][ny] == ".":
                dfs(nx, ny)

    vis = set()
    lakes = []
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    for i in range(n):
        for j in range(m):
            if grid[i][j] == "." and (i, j) not in vis:
                size = 0
                is_lake = True
                lake_cells = set()
                dfs(i, j)
                if is_lake:
                    lakes.append([size, lake_cells])

    lakes.sort()
    to_fill = len(lakes) - k
    cnt = 0

    ans = [list(row) for row in grid]
    for i in range(to_fill):
        cnt += lakes[i][0]
        for x, y in lakes[i][1]:
            ans[x][y] = "*"

    print(cnt)
    for row in ans:
        print("".join(row))

input = lambda: sys.stdin.readline().strip()

def main():
    solve()

if __name__ == '__main__':
    sys.setrecursionlimit(1 << 30)
    threading.stack_size(1 << 27)
    threading.Thread(target=main).start()

The problem gives us an undirected graph where every node has at least $$$k$$$ neighbors, and our task is to find a simple cycle (no repeated nodes) that has length at least $$$k + 1$$$. A cycle is a path that starts and ends at the same node, and all nodes in between are distinct.

The solution uses Depth-First Search (DFS) to explore the graph and try to find a cycle. While walking through the graph, we keep track of which nodes we've visited using a visited set, and we also keep a list called path_stack that stores the current path we're exploring in DFS. This path helps us reconstruct a cycle if we find one.

The key trick is to look for what's called a \textbf{back edge}. A back edge connects the current node to a node that has already been visited and is somewhere earlier in the current DFS path. When we find such a back edge, it means there is a cycle, and we can extract it from the path stack. But we have to be careful not to mistake a back edge to the immediate parent node for a real cycle. That's why the code checks if neighbor == parent and skips it. Otherwise, we'd wrongly think a node going back to its parent is a cycle of length $$$2$$$, which is not valid.

When we find a cycle, we check its length. If it's longer than $$$k$$$, then it's a valid answer, and we print it right away and stop the program. Since the problem guarantees that such a cycle exists, we don't need to search the whole graph—once we find one, we can safely exit.

Because the graph can be very large, we also increase the recursion limit and stack size using sys.setrecursionlimit and threading.stack_size. Python has a small default recursion stack, and without this change, the program could crash for big graphs.

Overall, the idea is simple: do a DFS, look for back edges that form cycles, and make sure the cycle is long enough. The parent check avoids false cycles, and the stack helps us extract the correct path.

import sys
import threading
from collections import defaultdict

# Increase the recursion limit and stack size to handle deep DFS
sys.setrecursionlimit(1 << 30)
threading.stack_size(1 << 27)


def main():
    def solve():
        # Read number of nodes (n), number of edges (m), and minimum cycle length (k)
        n, m, k = map(int, sys.stdin.readline().strip().split())

        # Build the undirected graph as an adjacency list
        graph = defaultdict(list)
        for _ in range(m):
            u, v = map(int, sys.stdin.readline().strip().split())
            graph[u].append(v)
            graph[v].append(u)

        visited = set()
        path_stack = []

        # Depth-First Search to find a cycle of length > k
        def dfs(current, parent):
            visited.add(current)
            path_stack.append(current)

            for neighbor in graph[current]:
                if neighbor == parent:
                    continue
                if neighbor not in visited:
                    dfs(neighbor, current)
                else:
                    # A back edge found, which indicates a cycle
                    if neighbor in path_stack:
                        cycle_start_index = path_stack.index(neighbor)
                        cycle = path_stack[cycle_start_index:]
                        if len(cycle) > k:
                            print(len(cycle))
                            print(*cycle)

                            # Exit the program immediately after finding the valid cycle
                            sys.exit(0)

            path_stack.pop()

        # Start DFS from node 1
        dfs(1, -1)

    solve()


# Run the main function in a new thread to support increased stack size
if __name__ == "__main__":
    thread = threading.Thread(target=main)
    thread.start()
    thread.join()