Install a Package with Its Dependencies

Install a Package with Its Dependencies Given a package dependency graph and a target package target, implement an installation procedure such that every package is installed only after all of its dependencies have been installed. Each package has an install() method. That method installs only the package itself and does not install dependencies automatically. Implement: install_with_dependencies(target, dependencies) Here, dependencies[p] is the list of direct dependencies of package p. Return the order in which install() is invoked. The order must include every direct and transitive dependency of target, and every dependency must occur before the package that depends on it. If there is a cyclic dependency reachable from target, do not perform a partial installation; report a cycle instead. Input Format (for this problem) First line: integer n, the number of dependency relations. Next n lines: package dependency, meaning package depends on dependency. Final line: target package name target. A package may appear on multiple lines to specify multiple dependencies. A package that never appears on the left-hand side has no dependencies. Output Format If no cycle exists: print one valid installation order with package names separated by spaces. If a cycle reachable from the target exists: print CYCLE. Example 1 Input: 4 app api app ui api auth ui auth app Output: auth api ui app The relative order of api and ui may differ, but auth must precede both and app must be last. Constraints 1 <= n <= 2 * 10^5 Package names are non-whitespace strings. Let V be the number of distinct packages and E the number of dependency relations. Example Input 4 app api app ui api auth ui auth app Output auth api ui app