[Here](https://codeforces.me/contestInvitation/a66de5ddf582f7d7ecf373014147caad99234d6b) is the contest link.↵
↵
↵
#### [A. Mahmoud and Ehab and the even-odd game](https://codeforces.me/gym/602812/problem/A)↵
↵
<spoiler summary="Hint 1">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
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.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python↵
↵
n = int(input())↵
if n % 2 == 0:↵
print("Mahmoud")↵
else:↵
print("Ehab")↵
```↵
</spoiler>↵
↵
#### [B. The Ethiopian Lakes](https://codeforces.me/gym/602812/problem/B)↵
↵
↵
<spoiler summary="Solution">↵
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).↵
↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Code"> ↵
```python ↵
↵
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)↵
↵
``` ↵
</spoiler>↵
↵
↵
↵
#### [C. Maedot's Apple Tree](https://codeforces.me/gym/602812/problem/C)↵
↵
<spoiler summary = "Solution">↵
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)$.↵
</spoiler>↵
↵
↵
<spoiler summary="Code - Recursive DFS">↵
```python3↵
↵
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])↵
```↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Code - Iterative DFS">↵
```python3↵
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])↵
↵
↵
```↵
</spoiler>↵
↵
#### [D. Lakes in Bahirdar](https://codeforces.me/gym/602812/problem/D)↵
↵
<spoiler summary = "Hint">↵
How do we find all lakes with their corresponding indices?↵
↵
<spoiler summary = "answer">↵
- Use DFS to explore each connected component of water ('.') and store its coordinates.↵
- If a water cell is connected to the border, it's not a lake.↵
↵
</spoiler>↵
↵
Which part of the lakes should we change to land?↵
↵
<spoiler summary = "answer">↵
- After collecting all valid lakes, sort them by size (smallest first).↵
- We need to remove the smallest (number of lakes — k) lakes by converting their cells to land ('*').↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary = "Solution">↵
↵
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.↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
↵
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()↵
↵
↵
↵
```↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
#### [E. Cycle in Graph](https://codeforces.me/gym/602812/problem/E)↵
↵
<spoiler summary="Solution">↵
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 `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.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python3↵
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()↵
```↵
</spoiler>↵
↵
↵
↵
#### [A. Mahmoud and Ehab and the even-odd game](https://codeforces.me/gym/602812/problem/A)↵
↵
<spoiler summary="Hint 1">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
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.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python↵
↵
n = int(input())↵
if n % 2 == 0:↵
print("Mahmoud")↵
else:↵
print("Ehab")↵
```↵
</spoiler>↵
↵
#### [B. The Ethiopian Lakes](https://codeforces.me/gym/602812/problem/B)↵
↵
↵
<spoiler summary="Solution">↵
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).↵
↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Code"> ↵
```python ↵
↵
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)↵
↵
``` ↵
</spoiler>↵
↵
↵
↵
#### [C. Maedot's Apple Tree](https://codeforces.me/gym/602812/problem/C)↵
↵
<spoiler summary = "Solution">↵
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)$.↵
</spoiler>↵
↵
↵
<spoiler summary="Code - Recursive DFS">↵
```python3↵
↵
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])↵
```↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Code - Iterative DFS">↵
```python3↵
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])↵
↵
↵
```↵
</spoiler>↵
↵
#### [D. Lakes in Bahirdar](https://codeforces.me/gym/602812/problem/D)↵
↵
<spoiler summary = "Hint">↵
How do we find all lakes with their corresponding indices?↵
↵
<spoiler summary = "answer">↵
- Use DFS to explore each connected component of water ('.') and store its coordinates.↵
- If a water cell is connected to the border, it's not a lake.↵
↵
</spoiler>↵
↵
Which part of the lakes should we change to land?↵
↵
<spoiler summary = "answer">↵
- After collecting all valid lakes, sort them by size (smallest first).↵
- We need to remove the smallest (number of lakes — k) lakes by converting their cells to land ('*').↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary = "Solution">↵
↵
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.↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
↵
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()↵
↵
↵
↵
```↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
#### [E. Cycle in Graph](https://codeforces.me/gym/602812/problem/E)↵
↵
<spoiler summary="Solution">↵
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 `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.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python3↵
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()↵
```↵
</spoiler>↵
↵
