CT64446

Minstrel's canals Reckoning

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Minstrel the paymaster watches over the honeycomb cliffs of Beeswick's stores of canals. A careful computation stands between order and chaos. 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 <= 1914; 0 <= m <= 1914.

Example 1:

Input: 429 1556 84 100 112 393 32 256 18 397 234 343 295 341 45 58 287 331 45 370 94 157 249 306 162 197 42 96 76 218 5 309 112 385 188 217 43 73 43 66 148 270 24 125 204 303 178 236 286 389 94 221 218 297 80 305 159 187 58 259 93 184 13 202 250 300 247 385 276 354 66 399 279 312 141 377 95 159 8 181 20 229 61 358 21 366 349 366 58 282 150 173 60 84 244 359 112 257 74 356 236 310 253 312 286 314 193 268 333 387 30 89 74 171 175 359 156 361 126 194 391 393 232 265 274 331 153 268 347 379 234 424 150 318 69 263 56 382 280 383 134 191 208 326 31 194 90 350 165 322 7 34 69 395 188 344 173 251 65 281 115 379 91 394 194 253 216 389 26 336 112 322 307 370 62 411 82 411 66 251 196 390 332 372 65 354 102 314 162 176 41 318 9 394 235 352 84 234 49 328 181 283 9 41 84 387 198 266 151 370 201 249 154 408 62 …
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 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 …

Example 2:

Input: 1174 1800 383 910 6 146 361 773 473 474 588 666 19 565 133 748 27 711 600 779 465 941 432 778 159 936 138 961 882 1016 673 739 178 1098 219 852 173 316 171 557 2 718 324 440 658 933 351 359 239 531 67 992 732 935 659 728 437 1161 149 417 97 1047 260 1045 437 804 541 934 251 749 650 683 491 1060 73 666 783 834 12 461 342 786 239 935 29 760 659 830 494 616 773 982 374 1006 71 88 102 330 70 583 18 55 168 456 165 808 153 263 1070 1155 192 533 90 1155 226 941 1002 1091 230 687 299 532 387 509 200 973 479 542 98 915 693 745 70 844 374 906 821 987 444 1066 190 973 546 1109 193 583 298 916 988 1093 2 355 844 1113 427 624 107 199 395 887 35 1162 681 992 851 1028 163 1076 732 802 395 520 83 334 616 1136 216 1131 391 1052 236 869 326 844 1065 1163 257 1150 324 891 174 206 358 518 817 1010 356 904 315…
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 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 …

Example 3:

Input: 37 205 16 23 6 29 1 5 17 22 3 15 1 13 23 28 3 14 7 14 9 11 26 37 15 31 18 21 3 35 18 31 21 36 3 7 3 20 5 36 6 31 8 28 13 25 17 23 13 20 6 24 11 27 21 37 21 26 16 20 15 36 14 25 6 33 28 33 28 31 4 20 25 26 19 32 16 18 7 32 12 36 9 16 2 6 13 27 17 20 5 30 23 29 4 22 11 30 23 25 25 32 6 8 16 25 8 13 4 10 7 11 6 11 20 28 5 32 25 37 9 33 17 35 18 29 1 9 7 36 10 23 11 12 2 30 7 18 10 22 5 37 14 20 15 28 9 19 8 21 19 21 14 28 9 29 20 34 24 35 5 24 14 33 26 29 30 37 15 32 3 9 33 34 5 22 10 37 11 37 18 37 27 30 13 21 12 22 31 32 3 34 2 19 8 20 13 16 4 34 16 35 15 26 7 9 4 37 35 36 4 12 26 35 13 34 1 20 1 21 2 23 1 33 4 8 18 36 11 29 8 34 7 8 15 27 27 29 6 30 12 35 1 2 27 28 13 30 14 17 10 29 11 28 21 34 10 26 2 14 7 23 3 31 9 12 7 34 31 34 13 33 23 37 16 33 9 14 21 29 4 29 25 27 19 31 30 33 19 35 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 <= 1914; 0 <= m <= 1914.

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