CT40952

Botanist and the Polished tunnels

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Botanist inherited the dairy at the lantern lake of Firefly Mere along with its curious bookkeeping system for tunnels. Time to make sense of it. 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 <= 1958; 0 <= m <= 1958.

Example 1:

Input: 29 52 23 27 7 29 13 27 14 22 4 5 3 20 5 17 4 7 10 23 4 6 8 21 12 28 14 27 5 6 11 14 18 28 7 8 7 24 13 29 5 27 12 29 1 19 4 18 3 12 5 23 28 29 5 14 18 19 11 19 17 28 12 26 12 25 8 22 6 19 3 22 16 22 21 25 9 22 5 10 16 19 10 12 6 15 16 18 11 26 2 24 2 5 1 16 13 22 9 19 7 23 10 28 7 26
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

Example 2:

Input: 723 1298 9 321 420 534 138 568 335 381 29 86 153 410 640 669 163 469 167 358 564 696 295 420 388 424 307 618 388 404 180 469 32 371 103 271 53 539 71 265 427 471 258 549 6 483 122 476 456 680 184 296 108 387 285 511 202 490 354 565 32 57 279 381 271 366 158 653 282 458 281 370 215 605 561 599 74 387 201 275 159 338 362 703 461 549 232 431 243 367 158 223 412 462 84 313 55 664 315 421 33 490 287 547 187 501 335 705 1 107 278 692 330 506 78 450 384 721 6 116 195 220 638 712 7 329 57 280 121 617 27 327 271 578 253 353 235 250 338 394 268 289 365 610 313 505 109 449 37 266 12 508 407 470 28 176 341 575 370 391 38 717 85 165 27 675 317 705 413 603 74 437 243 523 81 561 246 527 47 720 336 688 124 296 105 297 25 493 404 571 488 532 62 469 322 536 177 624 48 567 145 615 127 477 307 431 5 474 576 6…
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: 1537 726 157 1343 767 1431 836 1153 1227 1532 631 1529 498 882 1143 1398 647 739 340 1494 467 964 73 1481 615 1473 1015 1136 1156 1200 351 624 803 1229 497 915 74 858 587 1441 993 1388 1284 1399 951 1135 178 606 907 1419 978 1240 396 1329 333 1284 82 691 508 1526 247 751 1032 1405 638 1475 776 1490 431 530 632 1097 19 446 604 1122 1267 1383 351 399 1104 1214 873 912 785 1513 277 1200 839 1215 740 1384 830 1125 1035 1527 1130 1388 331 391 316 367 864 1280 909 1161 121 1424 428 617 969 992 678 969 131 446 610 1108 938 1332 549 1495 785 1071 92 229 362 1493 906 919 276 823 93 306 289 1428 44 52 41 928 44 519 1352 1494 391 732 1115 1403 938 1517 190 263 566 1448 575 1458 375 560 279 1251 339 1238 673 1091 377 910 40 1289 22 1127 126 574 1214 1519 5 469 519 877 33 1433 185 263 196 1511 837 1328…
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 <= 1958; 0 <= m <= 1958.

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