Compute dependency load factors in a DAG

System Dependency Load Factor

You are given:

• programs : a list of unique program names (strings)
• prerequisites : a list of pairs [a, b] meaning program a depends on program b

Considering only programs that appear in programs, these dependencies form a directed acyclic graph (DAG).

Load Factor

Define the Load Factor of a program x as the number of unique programs in programs that directly or indirectly depend on x.

• A program does not count as depending on itself.
• “Indirectly” means there exists a dependency chain (path) p -> ... -> x following edges a -> b (depends-on direction).

Data-cleaning rule

The input may contain prerequisite pairs involving programs not present in programs.

• If either a or b is not in programs , ignore that pair entirely (do not add either node or edge).

Task

Return a map/dictionary from each program name in programs to its Load Factor.

Example

Input

• programs = ["A", "B", "C", "D"]
• prerequisites = [["A","B"],["B","C"],["A","C"],["D","C"],["E","A"]]

(Notice ["E","A"] is ignored because E is not in programs.)

Output

• { "A": 0, "B": 1, "C": 3, "D": 0 }

Explanation (informal): C is depended on by A, B, and D → 3; B is depended on by A → 1.

Notes

• You may return the map in any key order.
• Assume the remaining graph (after ignoring invalid pairs) is a DAG.