Problem

At Meta, services such as News Feed, Ads Delivery, and Graph API can depend on other internal systems. Given a directed graph of system dependencies and a starting system, implement breadth-first search (BFS) to return the order in which systems are discovered, grouped by dependency distance.

A directed edge A -> B means system A depends directly on system B. Starting from start, traverse all reachable systems using BFS. Return two results:

1. The flat BFS traversal order.
2. A list of levels, where each level contains systems at the same distance from start.

Input / Output

• Input:
  • graph: a dictionary mapping each system name (string) to a list of directly dependent systems (list of strings)
  • start: a string representing the starting system
• Output:
  • A dictionary with keys:
    • order: list of strings in BFS visitation order
    • levels: list of lists of strings, grouped by BFS depth

Examples

Example 1 Input: graph = {"Feed": ["GraphAPI", "Cache"], "GraphAPI": ["Storage"], "Cache": ["Storage", "Metrics"], "Storage": [], "Metrics": []}, start = "Feed" Output: {"order": ["Feed", "GraphAPI", "Cache", "Storage", "Metrics"], "levels": [["Feed"], ["GraphAPI", "Cache"], ["Storage", "Metrics"]]}

Explanation: Feed is visited first, then its direct dependencies, then dependencies two hops away.

Example 2 Input: graph = {"Ads": ["Ranking", "Logging"], "Ranking": ["Models"], "Logging": [], "Models": []}, start = "Logging" Output: {"order": ["Logging"], "levels": [["Logging"]]}

Explanation: Logging has no outgoing dependencies, so traversal stops immediately.

Constraints

• 1 <= len(graph) <= 10^4
• Each adjacency list may be empty
• System names are non-empty strings
• The graph may contain cycles
• start is guaranteed to exist in graph