You are designing a route planner that suggests the best way to commute between two points in a city using different transportation modes. The city is represented as an undirected graph with `N` intersections labeled `0 .. N-1` and `M` roads. There are `K` possible commute modes (e.g., walk, bike, drive) labeled `0 .. K-1`. Each road is described as: - `u, v` — the two endpoints of the road (0-based node indices) - `allowed_modes` — a non-empty list of mode IDs in `0 .. K-1` that are allowed to travel on this road For every mode `m`: - If a road is usable by mode `m`, then traveling along that road: - takes `time_per_edge[m]` minutes - costs `cost_per_edge[m]` units of money You are also given: - an integer `S` — the starting intersection - an integer `D` — the destination intersection - an array `time_per_edge[0..K-1]` - an array `cost_per_edge[0..K-1]` ### Task 1. For every commute mode `m` in `0 .. K-1`, considering **only** roads whose `allowed_modes` contains `m`, compute the minimal number of edges from `S` to `D` (if reachable). From that, derive: - total travel time `T[m] = (number_of_edges_m) * time_per_edge[m]` - total travel cost `C[m] = (number_of_edges_m) * cost_per_edge[m]` If `D` is not reachable from `S` using mode `m`, then that mode should be considered **invalid** for the final choice. 2. Among all **valid** modes that can reach `D`, select the **optimal** commute mode according to: - smaller total travel time is better; - if two modes have the same total travel time, smaller total cost is better; - if both time and cost are equal, you may return any one of those modes. Return: - the chosen mode ID, and - the pair `(T[mode], C[mode])` for that chosen mode. If no mode can reach `D`, return an indication that the destination is unreachable (e.g., `-1` as the mode and some sentinel values for time and cost). Some modes may end up with identical `(time, cost)` pairs (duplicates); your algorithm must still handle these ties correctly. ### Constraints - `1 <= N <= 10^5` - `0 <= M <= 2 * 10^5` - `1 <= K <= 10` - The graph is sparse and fits in memory using adjacency lists. - All times and costs are non-negative integers that fit in 32-bit signed integers. ### Requirements - Exploit the fact that for each given mode, all usable roads have the **same** time and cost per edge. You should not treat this as an arbitrary weighted-graph problem that forces you to use a general algorithm like Dijkstra on a combined weighted graph for all modes. - The overall graph traversal per mode should run in linear time with respect to the size of the graph for that mode (i.e., `O(N + M)` per mode or better). - The final step that chooses the optimal mode from the `K` `(time, cost)` pairs must run in **O(K)** time and must **not** sort the list of modes. Describe your approach, discuss its time and space complexity, and then implement the solution in code.

def solution(N, roads, K, S, D, time_per_edge, cost_per_edge):
    from collections import deque

    adj = [[] for _ in range(N)]
    for u, v, allowed_modes in roads:
        mask = 0
        for m in allowed_modes:
            mask |= 1 << m
        adj[u].append((v, mask))
        adj[v].append((u, mask))

    results = []

    for m in range(K):
        bit = 1 << m
        dist = [-1] * N
        q = deque([S])
        dist[S] = 0

        while q:
            node = q.popleft()
            if node == D:
                break

            for nei, mask in adj[node]:
                if dist[nei] == -1 and (mask & bit):
                    dist[nei] = dist[node] + 1
                    q.append(nei)

        if dist[D] == -1:
            results.append((-1, -1, -1))
        else:
            edges = dist[D]
            results.append((edges, edges * time_per_edge[m], edges * cost_per_edge[m]))

    return results

def solution(mode_metrics):
    best_mode = -1
    best_time = -1
    best_cost = -1

    for mode, (time, cost) in enumerate(mode_metrics):
        if time < 0 or cost < 0:
            continue

        if best_mode == -1 or time < best_time or (time == best_time and cost < best_cost):
            best_mode = mode
            best_time = time
            best_cost = cost

    if best_mode == -1:
        return (-1, (-1, -1))

    return (best_mode, (best_time, best_cost))