To check if an amount $$$n$$$ can be formed using coins of denominations $$$2$$$ and $$$k$$$ (with $$$k \ne 2$$$), we can simplify the problem using a key observation: two $$$k$$$-coins can be replaced by $$$k$$$ coins of $$$2$$$, since $$$2k = k \cdot 2$$$.

This means any solution using two or more $$$k$$$-coins can be transformed into one with at most one $$$k$$$-coin. So, we only need to check two cases:

Use only $$$2$$$-coins: possible if $$$n$$$ is even.

Use one $$$k$$$-coin and the rest $$$2$$$-coins: possible if $$$n \ge k$$$ and $$$n - k$$$ is even.

If either condition holds, the answer is "YES"; otherwise, it's "NO". This allows each test case to be solved in constant time.

t = int(input())
for _ in range(t):
    n, k = map(int, input().split())
    if n % 2 == 0 or (n >= k and (n - k) % 2 == 0):
        print("YES")
    else:
        print("NO")

In this problem, we are given a sequence of cells arranged in a line (from $$$1$$$ to $$$n$$$) with portals between some of them. The portals are one-way and described using an array $$$a$$$, where each element $$$a_i$$$ tells us that from cell $$$i$$$, we can move forward to cell $$$i + a_i$$$. We begin at cell $$$1$$$ and are asked to determine whether we can reach cell $$$t$$$ using only the available portals.

This structure can be interpreted as a directed graph, where each node (cell) has exactly one outgoing edge (as described by the portals). Since we only move forward and there is no branching (each node goes to exactly one next node), we can simulate this as a simple linear traversal—essentially a simplified depth-first search (DFS) or a loop—starting from cell $$$1$$$ and following the portals until we either reach cell $$$t$$$ or go past it.

We continue moving from the current cell to the next one given by the portal, i.e., from $$$i$$$ to $$$i + a_i$$$, and check at each step whether we've landed at cell $$$t$$$. If we do, we output "YES". If we go beyond it or reach a point from which we can no longer progress toward $$$t$$$, we conclude it's unreachable and output "NO."

This logic runs in linear time and is highly efficient due to the constraint that each cell leads to only one next cell.

n, t = map(int, input().split())
a = list(map(int, input().split()))

pos = 1
while pos < t:
    pos += a[pos - 1]

if pos == t:
    print("YES")
else:
    print("NO")

We are given a grid where each cell contains a non-negative integer representing the depth of water. A lake is defined as a group of connected cells (connected up, down, left, or right) that all have positive depth (greater than zero). Our goal is to find the lake with the largest total volume, where volume is the sum of depths of all cells in that lake.

To solve this, we can use either Depth-First Search (DFS) or Breadth-First Search (BFS). The idea is to explore the grid cell by cell. Whenever we find a cell with depth greater than zero that we haven’t visited before, we start a DFS/BFS from that cell to find all connected cells belonging to the same lake. During this traversal, we accumulate the total depth (volume) of the lake.

After completing the search for a lake, we compare its volume with the maximum volume found so far and update if needed. We repeat this process until all cells have been checked.

This approach ensures that each cell is visited at most once, resulting in an overall time complexity of $$$O(nm)$$$ where $$$n$$$ and $$$m$$$ are the grid dimensions. This is efficient enough given the problem constraints.

Implementing the search iteratively (using a stack for DFS or a queue for BFS) instead of recursively often gives better performance in practice, avoiding the overhead and limitations of recursion and reducing the risk of stack overflow on large inputs.

import sys
input = sys.stdin.readline

t = int(input())
directions = [(1,0), (-1,0), (0,1), (0,-1)]

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
    
    for i in range(n):
        for j in range(m):
            if grid[i][j] > 0 and not visited[i][j]:
                stack = [(i,j)]
                volume = 0
                visited[i][j] = True
                
                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 grid[nx][ny] > 0 and not visited[nx][ny]:
                                visited[nx][ny] = True
                                stack.append((nx, ny))
                
                if volume > max_volume:
                    max_volume = volume
    
    print(max_volume)

The problem models a 3D plate composed of $$$k$$$ layers, each layer being a 2D grid of size $$$n \times m$$$. Some cells are empty '.', where water can fill, and some contain obstacles '#' that block water flow. Water starts pouring from a specific cell in the top layer and flows to adjacent cells in all 6 directions — up, down, left, right, forward, and backward — but only through empty cells.

To determine how many units of water the plate can hold before overflowing, the key is to find how many empty cells are reachable from the starting tap position. Each reachable empty cell can hold exactly one unit of water. Therefore, the answer is the count of all connected empty cells accessible from the tap.

The solution treats the plate as a 3D grid and performs a Depth-First Search (DFS) starting from the tap’s cell in the top layer. DFS explores all neighboring cells in the six possible directions — vertically between layers, horizontally between rows, and laterally between columns — as long as those cells are within bounds, empty, and not yet visited. This exploration simulates the spread of water filling every reachable empty cell.

The code first reads the 3D grid input carefully, handling blank lines between layers, and converts the coordinates of the tap to zero-based indexing. Then, it initializes a 3D visited array to keep track of cells already counted. The DFS uses an explicit stack to avoid recursion limits and traverses all accessible cells, counting each as water volume.

Finally, the total count of reachable cells represents how many minutes until the plate is completely filled (since one unit of water falls each minute). If the water falls beyond this count, it would overflow, so the answer is this count.

This approach efficiently solves the problem in time complexity $$$O(kmn)$$$ since each cell is visited at most once, which is practical given the problem constraints.

def read_3d_grid():
    d, r, c = map(int, input().split())
    grid = []
    layers_read = 0

    while layers_read < d:
        line = input().strip()
        if line == "":
            continue
        layer = [list(line)]
        for _ in range(r - 1):
            layer.append(list(input().strip()))
        grid.append(layer)
        layers_read += 1

    while True:
        start_line = input().strip()
        if start_line:
            break

    start_x, start_y = map(int, start_line.split())
    start_x -= 1
    start_y -= 1

    return d, r, c, grid, start_x, start_y


def in_bounds(z, x, y, d, r, c):
    return 0 <= z < d and 0 <= x < r and 0 <= y < c


def dfs(z, x, y, grid, visited, d, r, c):
    stack = [(z, x, y)]
    visited[z][x][y] = True
    minutes = 0

    directions = [
        (1, 0, 0), (-1, 0, 0),
        (0, 1, 0), (0, -1, 0),
        (0, 0, 1), (0, 0, -1)
    ]

    while stack:
        cz, cx, cy = stack.pop()
        minutes += 1

        for dz, dx, dy in directions:
            nz, nx, ny = cz + dz, cx + dx, cy + dy
            if in_bounds(nz, nx, ny, d, r, c):
                if not visited[nz][nx][ny] and grid[nz][nx][ny] == '.':
                    visited[nz][nx][ny] = True
                    stack.append((nz, nx, ny))

    return minutes


d, r, c, grid, start_x, start_y = read_3d_grid()
visited = [[[False for _ in range(c)] for _ in range(r)] for _ in range(d)]

start_layer = 0

if grid[start_layer][start_x][start_y] == '.':
    minutes_until_overflow = dfs(start_layer, start_x, start_y, grid, visited, d, r, c)
else:
    minutes_until_overflow = 0

print(minutes_until_overflow)

We are given a graph with $$$n$$$ nodes and $$$m$$$ edges. Among these nodes, $$$k$$$ are designated as government nodes. The graph is stable, which means each connected component contains at most one government node, and there are no paths between different government nodes. Our task is to add as many new edges as possible while keeping the graph stable.

The first step is to analyze each connected component of the graph. In any single component, as long as it contains at most one government node, we are free to add edges. The optimal way to do this is to turn each component into a complete graph (clique), where every pair of nodes is connected. For a component of size $$$s$$$, the maximum number of edges it can contain is $$$s \cdot (s - 1) / 2$$$. If the component currently has $$$e$$$ edges, then we can add $$$s \cdot (s - 1) / 2 - e$$$ new edges.

Some components may not contain any government node. These components can be safely merged with a government component without violating stability, because the resulting component will still have at most one government node. To maximize the number of new edges, we should merge all non-government components into the largest government component. This is because merging a component of size $$$a$$$ with one of size $$$b$$$ allows us to add $$$a \cdot b$$$ new edges. So, the more nodes the government component has, the more beneficial the merge becomes.

To implement the solution, we use depth-first search (DFS) or union-find to identify all connected components and determine which ones have government nodes. We then calculate the number of edges we can add to make each component a clique. After identifying the non-government components, we calculate their total size and merge them into the largest government component, adding $$$x \cdot L$$$ additional edges, where $$$x$$$ is the number of non-government nodes and $$$L$$$ is the size of the largest government component.

The final answer is the sum of all possible new edges minus the $$$m$$$ edges that already exist.

This approach runs in linear time relative to the number of nodes and edges, with an overall time complexity of $$$O(n + m)$$$.

def solve():
    import sys
    input = sys.stdin.readline

    n, m, k = map(int, input().split())
    special = set(map(int, input().split()))

    graph = [[] for _ in range(n + 1)]
    for _ in range(m):
        u, v = map(int, input().split())
        graph[u].append(v)
        graph[v].append(u)

    visited = [False] * (n + 1)

    def dfs(start):
        stack = [start]
        visited[start] = True
        size = 0
        has_special = False
        while stack:
            node = stack.pop()
            size += 1
            if node in special:
                has_special = True
            for neighbor in graph[node]:
                if not visited[neighbor]:
                    visited[neighbor] = True
                    stack.append(neighbor)
        return size, has_special

    def combination(x):
        return x * (x - 1) // 2

    total_non_special = 0
    largest_special_size = 0
    special_sum = 0

    for i in range(1, n + 1):
        if not visited[i]:
            size, has_special = dfs(i)
            if has_special:
                special_sum += combination(size)
                largest_special_size = max(largest_special_size, size)
            else:
                total_non_special += size

    # Recalculate contribution of largest special component
    special_sum -= combination(largest_special_size)
    special_sum += combination(largest_special_size + total_non_special)

    result = special_sum - m
    print(result)

solve()

We are given a connected undirected graph with $$$n$$$ vertices and $$$m$$$ edges. The task is to remove exactly one edge so that the number of vertex pairs $$$(u, v)$$$ with $$$1 \le u \lt v \le n$$$ that are still connected by some path becomes as small as possible.

Initially, since the graph is connected, every pair of vertices is reachable. This means there are $$$\frac{n \cdot (n - 1)}{2}$$$ reachable pairs. If we remove any edge that is not a bridge, the graph remains connected, and the number of reachable pairs stays exactly the same. So, in order to reduce the number of reachable pairs, we must remove a bridge.

A bridge is an edge whose removal increases the number of connected components in the graph. In other words, if we remove a bridge, the graph splits into two disconnected components. Let the sizes of these two components be $$$x$$$ and $$$y$$$, where $$$x + y = n$$$. After the split, only pairs within the same component remain reachable. So the new number of reachable pairs becomes $$$\frac{x \cdot (x - 1)}{2} + \frac{y \cdot (y - 1)}{2}$$$.

Our goal is to find the bridge whose removal results in the smallest possible total of reachable pairs. To do that, we can perform a DFS traversal to find all bridges in the graph. While doing so, we also compute the subtree size for each node. Suppose we are processing a bridge edge $$$(u, v)$$$ where $$$v$$$ is in the subtree of $$$u$$$. Then, one of the resulting components will have size equal to the subtree size of $$$v$$$, and the other will have size $$$n - \text{subtree}[v]$$$.

For every bridge, we calculate the number of reachable pairs after its removal using the formula above, and we keep track of the minimum among them. If no bridges exist, then removing any edge won't disconnect the graph, and the answer remains $$$\frac{n \cdot (n - 1)}{2}$$$.

This solution is efficient. Finding bridges and computing subtree sizes via DFS both take linear time, so each test case runs in $$$O(n + m)$$$ time. Since the total sum of $$$n$$$ and $$$m$$$ over all test cases is limited to $$$2 \cdot 10^5$$$, the solution fits comfortably within the time limits.

import sys
input = sys.stdin.readline

def solve():
    t = int(input())
    for _ in range(t):
        n, m = map(int, input().split())
        graph = [[] for _ in range(n + 1)]
        for _ in range(m):
            u, v = map(int, input().split())
            graph[u].append(v)
            graph[v].append(u)

        tin = [0] * (n + 1)
        low = [0] * (n + 1)
        visited = [False] * (n + 1)
        size = [1] * (n + 1)
        bridges = []

        timer = 1
        stack = []
        parent = [-1] * (n + 1)
        neighbors_idx = [0] * (n + 1)

        stack.append(1)
        visited[1] = True
        tin[1] = low[1] = timer
        timer += 1

        while stack:
            u = stack[-1]
            if neighbors_idx[u] < len(graph[u]):
                v = graph[u][neighbors_idx[u]]
                neighbors_idx[u] += 1

                if v == parent[u]:
                    continue

                if not visited[v]:
                    visited[v] = True
                    tin[v] = low[v] = timer
                    timer += 1
                    parent[v] = u
                    stack.append(v)
                else:
                    low[u] = min(low[u], tin[v])
            else:
                stack.pop()
                p = parent[u]
                if p != -1:
                    low[p] = min(low[p], low[u])
                    size[p] += size[u]
                    if low[u] > tin[p]:
                        # Found a bridge between p and u
                        bridges.append((p, u))

        total_pairs = n * (n - 1) // 2

        if not bridges:
            print(total_pairs)
            continue

        max_cut = 0
        for u, v in bridges:
            x = min(size[u], size[v])

            part1_after_cut = (n - x) * (n - x - 1) // 2
            part2_after_cut = x * (x - 1) // 2

            cut_value = total_pairs - (part1_after_cut + part2_after_cut)

            max_cut = max(max_cut, cut_value)

        print(total_pairs - max_cut)

solve()