CT40851

Gino and the Scarlet corridors

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Gino found an old ledger of corridors in the dairy attic at the thorn maze of Bramblecourt. The margin notes pose a precise question. 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 <= 3107; 0 <= m <= 3107.

Example 1:

Input: 365 303 10 185 9 344 186 356 123 174 47 82 149 153 36 106 110 274 226 342 118 213 173 260 41 75 6 87 51 218 5 80 126 346 173 232 63 310 30 137 81 341 132 170 74 280 62 186 79 83 316 365 261 320 132 150 126 354 91 350 26 201 95 331 34 280 90 291 255 264 16 151 78 151 284 354 58 155 208 310 285 295 273 324 6 258 132 299 186 193 214 291 38 68 3 20 13 48 23 159 223 289 286 343 319 323 8 215 321 347 71 207 27 54 73 112 70 260 174 190 56 304 225 355 259 337 195 334 32 312 83 92 192 238 58 355 223 241 17 300 164 265 92 200 85 158 109 162 102 304 198 267 217 243 89 208 39 224 64 225 208 342 19 123 141 288 170 320 268 349 194 311 12 243 330 336 98 301 169 242 104 163 26 81 20 234 249 253 192 349 35 142 11 342 36 255 24 116 42 320 6 249 123 231 87 191 273 351 101 200 313 357 92 198 70 266 33 285 57 …
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: 2684 169 1248 2539 731 1960 117 1711 2330 2544 1090 1225 244 457 323 2082 1083 2612 532 2604 318 1877 817 940 1757 1769 1404 2248 648 1540 1763 2122 432 2308 28 1482 321 1837 25 1139 847 2417 1087 2424 1300 1740 238 2261 1126 2223 1750 2504 84 2582 1517 1751 642 1097 324 531 283 975 311 2337 246 1445 1885 2081 473 1383 235 883 771 2092 2600 2625 1414 2522 1655 2521 372 2455 590 795 621 1361 984 1309 373 1692 1961 2592 634 1715 2144 2386 134 2500 1345 2038 416 2226 1222 1696 1155 1545 1279 2348 27 719 725 1669 297 594 1968 2399 358 825 1575 2357 377 474 25 2480 287 2477 401 409 395 990 799 1807 319 1003 411 2131 95 999 431 1486 1252 1620 270 1365 728 2556 1896 2275 113 1299 472 1207 1127 1740 1270 1344 10 1856 1532 2267 506 1674 2059 2524 1475 1692 376 1685 590 1860 779 1010 1365 1654 907 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 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: 1448 2095 817 1198 70 927 750 966 522 622 391 1339 363 486 814 1199 765 827 92 583 553 880 228 773 119 1405 243 1119 350 940 35 706 46 552 900 1106 176 871 67 524 655 849 81 984 1 751 209 1342 1123 1246 116 774 1015 1325 27 97 888 1045 37 1423 116 291 226 850 269 1204 338 811 784 1390 234 828 355 357 901 978 727 1306 942 1404 302 485 222 990 669 1380 1291 1384 946 1381 787 1427 999 1337 694 970 742 871 211 1415 4 1298 479 1097 319 1240 1152 1299 440 655 228 1191 561 736 1054 1186 871 1000 1022 1423 155 312 553 802 1112 1423 11 979 1014 1100 1008 1448 265 613 714 1348 866 1155 721 762 196 1281 734 881 50 1046 592 826 11 1436 428 1009 99 1244 557 1057 404 1423 3 676 703 1197 891 1223 347 798 259 521 686 983 367 998 528 810 599 1309 1227 1228 448 865 130 453 166 799 306 972 1193 1354 2 968 47…
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 …

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Gino and the Scarlet corridors - MEDIUM Coding Problem | CodeTikki