CT60927

The Build Order Beneath Sleekwater

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Legend says the vault under the otter slides of Sleekwater opens only for a perfect tally of canals. Boris means to find out. 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 <= 1802; 0 <= m <= 1802.

Example 1:

Input: 1617 552 336 581 282 1189 385 1517 249 396 564 1336 8 360 333 358 322 1353 382 835 676 806 279 1216 640 833 322 701 926 1197 43 493 1187 1246 65 1552 1170 1532 90 979 831 1184 1389 1427 423 1467 245 740 33 1269 170 471 593 1500 1060 1399 235 889 1475 1583 649 1582 102 388 700 898 355 1487 591 966 162 644 1194 1580 27 390 446 942 1008 1037 588 816 40 181 1267 1340 579 1286 725 914 1341 1425 740 1274 16 167 448 1321 29 1425 623 1443 718 1049 994 1061 1139 1292 209 1244 846 1323 631 1048 176 760 1233 1439 654 1475 44 292 459 1204 105 1302 198 230 819 1313 108 1573 35 698 414 1602 966 1336 5 1054 269 704 248 267 839 1116 1271 1287 1060 1584 318 1391 422 659 780 1365 1192 1558 1489 1498 625 1326 933 1532 81 853 273 878 89 947 409 631 572 1222 1401 1554 270 1024 263 593 681 1012 541 808 693 1320…
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: 607 997 379 500 226 272 311 398 433 539 13 114 361 496 92 305 76 596 398 525 200 364 423 441 201 331 166 356 252 348 287 357 312 536 500 575 99 412 109 432 34 269 224 418 275 297 143 166 26 278 296 531 208 370 264 464 13 467 68 460 4 65 57 586 8 172 103 113 33 287 41 351 116 174 372 605 37 566 115 591 456 514 148 462 246 379 170 552 48 364 186 415 325 605 107 312 209 332 536 598 52 72 66 282 405 496 78 375 406 531 24 143 1 202 216 603 290 474 175 539 111 279 3 448 399 523 375 504 41 315 8 28 176 533 33 176 348 415 300 327 114 178 190 598 56 563 41 72 4 193 25 515 13 179 331 345 368 402 193 496 69 376 290 291 5 384 225 572 490 556 5 37 100 155 444 539 170 326 123 554 492 603 96 439 511 579 291 347 280 472 582 605 5 460 226 482 406 459 87 433 36 386 407 518 290 544 267 327 39 577 29 446 147 …
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: 1684 320 531 1288 377 1428 709 813 1497 1533 603 737 455 721 209 474 936 1252 1379 1635 207 404 1 176 473 767 763 1093 958 1379 906 1667 142 500 777 998 368 377 288 1271 114 1006 804 1292 214 766 617 631 964 1041 562 873 930 1201 216 1080 1154 1419 1521 1557 422 1270 1272 1341 1607 1678 240 900 1177 1205 262 1307 485 1236 231 938 635 1554 900 1360 55 635 120 183 605 1213 92 860 1049 1149 1085 1649 363 1432 626 669 493 1282 807 980 1051 1551 562 753 1209 1406 727 1534 16 1263 428 1257 20 145 744 1672 402 619 448 1081 1336 1373 648 1104 448 1650 10 1017 829 1058 840 1407 884 888 1667 1673 272 984 985 1390 129 869 167 220 1016 1244 454 1178 905 971 418 965 760 1052 293 1326 607 1160 127 927 848 1084 438 1013 1245 1655 139 1020 1130 1348 642 649 56 1576 188 1610 51 128 495 1317 539 829 622 158…
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 <= 1802; 0 <= m <= 1802.

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