Count probe routes
A network team counts the diagnostic routes a probe could take. link_ms is a square table where link_ms[a][b] is the one way latency in milliseconds of the link from node a to node b, and 0 means there is no link, including every entry on the diagonal. The table is not always symmetric. A route starts at node 0, ends at the last node, never visits a node twice, totals at most budget milliseconds, and passes through every node listed in must_visit. must_visit may repeat a node and may name the start or the end. Return how many such routes exist. Return 0 when the table has no nodes. A table with a single node gives one route, the one that has already arrived, whenever budget is not negative. There are at most 12 nodes.
count_relay_routes(link_ms: list[list[int]], budget: int, must_visit: list[int]) → int[[[0,4,9],[4,0,3],[9,3,0]],12,[]]out2[[[0,4,9],[4,0,3],[9,3,0]],12,[1]]out1[[[0,4,9],[4,0,3],[9,3,0]],6,[]]out0State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
[[[0,4,9],[4,0,3],[9,3,0]],12,[]]2not run yetsample[[[0,4,9],[4,0,3],[9,3,0]],12,[1]]1not run yetsample[[[0,4,9],[4,0,3],[9,3,0]],6,[]]0not run yetsample