Server Message Distances Avoiding Failed Servers and Their Failure Radius

Servers in a network pass messages to each other over undirected links, and every link counts as one hop. Some servers have failed, and a failure also takes down every server within a given number of hops of the failed server. Given a start server, return the shortest hop distance from it to every healthy server that a message can reach. The interview built this up in four steps: first the shortest distance between two servers, then whether a message can get from one server to another without passing through a failed server, then the distances from a start server to every reachable healthy server, and finally failures that also disable every server within a radius. This console asks for the final step, and the earlier steps are special cases of it: with an empty `failed` list nothing is disabled, with `radius = 0` only the failed servers themselves are, and the distance to a particular server, or whether it can be reached at all, is read off the returned list. ### Function Signature ```python def distances_after_failures(n: int, edges: list[list[int]], start: int, failed: list[int], radius: int) -> list[list[int]]: ``` ### Rules - The servers are labelled `0` to `n - 1`. Each `[u, v]` in `edges` is an undirected link of length 1 between servers `u` and `v`. - `start` and the entries of `failed` may be `n` or larger; such an id names a server that does not exist. A failed server that does not exist disables nothing. - A server is **disabled** when its shortest distance in the full original graph to at least one existing failed server is at most `radius`. That distance counts every link, including links that pass through other failed or disabled servers. A failed server is at distance 0 from itself, so it is always disabled. - Disabled servers do not spread the failure further: the radius is measured from the failed servers only, never from the servers they take down. - If `start` does not exist or is disabled, return an empty list. A failed or disabled start reaches nothing, not even itself. - Otherwise a message leaves `start` and travels along links, passing through and arriving at servers that are not disabled only. For every such server it can reach, including `start` itself at distance 0, report the smallest number of links on such a path. - Return a list of `[server, distance]` pairs, one per reachable server that is not disabled, sorted by `server` in ascending order. Disabled and unreachable servers do not appear. ### Constraints - `1 <= n <= 10^5` - `0 <= len(edges) <= 2 * 10^5`; for every edge `0 <= u, v <= n - 1` and `u != v`, and no link is listed twice. - `0 <= start <= 2 * 10^5` - `0 <= len(failed) <= 10^5`; the entries of `failed` are distinct integers in `[0, 2 * 10^5]`. - `0 <= radius <= 10^5` - The graph need not be connected. ### Examples All three examples use the same network: ```text n = 9 edges = [[1, 3], [3, 4], [4, 8], [1, 2], [2, 6], [6, 7], [7, 8], [0, 5]] 1 --- 3 --- 4 --- 8 | | 2 --- 6 --- 7 ----+ 0 --- 5 ``` **Example 1** ```text Input: n = 9, edges = (above), start = 1, failed = [], radius = 0 Output: [[1, 0], [2, 1], [3, 1], [4, 2], [6, 2], [7, 3], [8, 3]] ``` No server has failed. The shortest path from 1 to 8 is 1 → 3 → 4 → 8, three links; the route through 2, 6 and 7 takes four. Servers 0 and 5 are in a separate component, so they are unreachable and do not appear. **Example 2** ```text Input: n = 9, edges = (above), start = 1, failed = [4], radius = 0 Output: [[1, 0], [2, 1], [3, 1], [6, 2], [7, 3], [8, 4]] ``` Only server 4 is disabled. Server 3 is still reachable, but nothing lies beyond it, and a message to 8 must now take 1 → 2 → 6 → 7 → 8, four links. **Example 3** ```text Input: n = 9, edges = (above), start = 1, failed = [6, 12], radius = 1 Output: [[1, 0], [3, 1], [4, 2], [8, 3]] ``` Server 12 does not exist and disables nothing. Server 6 and its neighbours 2 and 7 are within one link of the failure, so all three are disabled. From 1 the message reaches 3, 4 and 8 along the top row; the only other link out of 8 leads to the disabled server 7.