A renderer schedules n passes (labeled 0..n-1). A directed edge u v means pass u must run before pass v. Among all valid orderings, output the lexicographically smallest one, comparing orderings as sequences of pass labels. If no valid ordering exists (the constraints contain a cycle), output CYCLE instead.
The lexicographically smallest order is obtained greedily: at each step, from all passes whose prerequisites are already scheduled, choose the one with the smallest label.
Line 1: two integers n and m — the number of nodes (labeled 0 through n-1) and the number of directed edges.
Each of the next m lines: two integers u v, a directed edge from u to v (read as: u must come before v).
If a valid ordering exists, print the lexicographically smallest one as n space-separated labels on one line. Otherwise print CYCLE.
Example 1
Input
3 2 0 2 1 2
Expected
0 1 2
Explanation
Both 0 and 1 must precede 2. Choosing the smallest ready label each step gives 0, then 1, then 2.
Example 2
Input
2 2 0 1 1 0
Expected
CYCLE
Explanation
0 must precede 1 and 1 must precede 0 — a cycle, so no ordering exists: CYCLE.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →