CT60382

The Build Order at Rye Hollow

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

In the gristmill of Rye Hollow, Jatin the clerk keeps careful count of the canals. Prepare the expedition manifest, every figure matters. Task: Edges u -> v mean u must come before v. Print the lexicographically smallest valid ordering of the n jobs (space-separated), or IMPOSSIBLE if a cycle exists. Input format: First line: n and m. Next m lines: u v. Output format: Print the order or IMPOSSIBLE. Constraints: 1 <= n <= 770; 0 <= m <= 770.

Example 1:

Input: 38 465 4 17 2 30 15 36 1 23 13 31 21 38 4 36 13 16 2 37 9 30 28 34 11 37 18 21 23 37 8 10 16 37 6 28 30 32 4 14 20 33 10 15 23 30 21 27 24 30 20 38 6 22 2 6 24 31 22 34 19 23 5 10 9 19 16 21 5 14 13 30 29 33 27 34 9 10 3 31 29 31 4 23 27 37 24 35 14 34 27 28 6 7 12 37 3 37 32 36 22 29 5 36 6 13 6 36 30 38 4 29 8 26 18 22 2 22 8 30 13 19 10 25 25 27 2 24 6 35 1 27 10 28 14 32 5 18 6 23 26 35 30 35 12 15 7 24 15 20 7 22 16 20 15 24 8 36 15 34 29 37 6 12 12 21 12 27 2 13 15 22 5 19 18 20 17 28 9 31 13 35 7 16 35 38 24 38 5 34 9 16 7 12 1 5 18 37 8 12 12 20 18 36 7 28 3 12 35 36 4 30 5 16 4 9 8 19 20 34 3 28 1 18 5 9 16 29 8 25 18 25 9 25 20 27 18 35 25 35 1 6 34 36 11 24 4 32 19 32 11 23 19 26 8 28 4 27 3 23 15 21 13 26 25 26 16 26 10 38 14 28 12 36 32 35 11 29 19 20 5 6 3 26 12 22 24 28 11 1…
Output: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

Example 2:

Input: 94 622 55 74 33 75 57 66 66 71 26 59 49 58 1 3 7 84 19 87 8 53 35 60 38 74 45 57 45 88 5 84 9 28 7 35 11 53 12 89 22 35 30 36 3 87 41 77 49 60 21 87 33 56 78 81 6 56 45 59 37 44 46 47 35 88 29 44 12 40 89 91 46 75 28 69 28 60 89 92 27 60 23 71 26 57 53 63 17 72 15 24 10 61 50 74 10 55 18 40 1 89 6 59 56 78 32 51 28 48 54 84 15 62 27 46 53 90 30 44 63 90 36 93 66 73 42 49 22 75 56 67 50 79 7 14 48 60 2 79 40 67 29 36 21 23 58 59 6 90 35 90 15 35 5 71 6 37 3 67 15 94 26 61 13 84 43 79 6 24 54 68 26 85 81 82 3 62 11 31 17 18 74 77 23 28 3 36 50 86 10 57 17 50 29 74 14 35 50 70 4 35 33 86 5 54 10 51 21 74 18 51 45 79 37 67 16 68 46 69 5 12 21 46 40 61 38 65 23 32 25 88 14 30 46 67 11 85 15 26 3 31 25 61 5 22 56 83 28 55 1 20 1 36 42 46 16 89 13 33 26 84 51 94 12 33 17 84 20 24 21 33 28 70 15 8…
Output: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94

Example 3:

Input: 37 310 8 32 5 26 10 31 13 19 26 35 2 18 10 13 7 37 11 16 7 36 1 16 22 34 8 19 29 33 24 28 14 29 22 29 16 17 3 24 21 31 4 27 22 32 25 28 8 11 22 25 3 5 33 34 3 4 3 31 18 31 11 32 10 33 18 27 22 37 5 7 2 35 15 37 11 29 2 5 21 36 3 10 11 31 7 15 22 30 10 28 21 35 6 12 3 13 12 16 16 34 7 23 4 37 20 34 27 36 18 28 14 17 1 14 19 32 7 20 31 34 10 29 33 37 32 34 10 24 26 31 27 35 10 30 9 11 7 33 12 37 8 25 4 23 23 30 19 33 7 27 1 9 19 31 1 11 12 13 5 30 6 23 12 33 19 26 4 26 11 19 18 22 26 28 24 37 35 37 24 25 7 17 30 31 7 30 23 25 6 35 29 34 14 22 13 17 1 36 11 21 25 32 17 25 10 16 27 31 30 32 9 34 10 14 14 32 11 18 13 36 5 24 15 33 19 27 6 13 1 15 9 22 14 16 17 28 6 8 5 20 27 30 6 36 17 20 8 27 8 15 16 28 13 31 19 25 14 26 2 24 16 20 24 32 15 22 28 29 19 20 8 26 3 19 23 37 16 31 30 34 3 33 1 8 2…
Output: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

Constraints:

1 <= n <= 770; 0 <= m <= 770.

Loading...
Test Cases:No test cases
No test cases available.