Package Dependency Installation Order

Problem: Package Dependency Management and Installation Order Design a package dependency manager. Each package is identified by a unique string. A dependency pair [package, dependency] means that dependency must be installed before package. Implement a function that returns a valid installation order for a target package and all of its direct and transitive dependencies. Requirements: Include the target package and every package reachable through its dependencies. Each package may appear at most once. Every dependency must appear before the package that depends on it. Return an empty list if a dependency cycle makes installation impossible. A dependency that never appears on the left side of a pair is still a valid leaf package. Function Signature def get_install_order(target: str, dependencies: list[tuple[str, str]]) -> list[str]: Example 1 target = "app" dependencies = [ ("app", "ui"), ("app", "service"), ("service", "database"), ("ui", "common"), ("database", "common") ] One valid output is: ["common", "ui", "database", "service", "app"] Example 2 target = "A" dependencies = [("A", "B"), ("B", "C"), ("C", "A")] Output: [] Constraints 0 <= m <= 200,000 dependency pairs. Total package-name length is at most 2 * 10^6. Avoid recursion-depth failures on deep graphs. Example Input app 5 app ui app service service database ui common database common Output common ui database service app