CT59915

The roads at Coralcove

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Tarun the scribe watches over the island market of Coralcove's stores of roads. 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 <= 1532; 0 <= m <= 1532.

Example 1:

Input: 1221 1478 299 459 646 1159 476 1077 201 579 401 443 213 1073 311 363 736 1057 831 1168 456 580 57 447 511 1008 64 617 257 286 203 271 442 711 238 245 28 565 230 483 984 1134 579 880 721 1079 788 1103 318 867 833 901 398 614 140 987 82 355 169 1075 395 1117 964 1167 141 1197 778 1051 412 534 634 751 152 501 1015 1188 297 628 934 1202 810 1145 502 798 600 1186 59 1165 598 680 153 316 99 471 221 764 764 801 494 957 167 1182 60 1039 740 756 32 998 296 1040 124 1171 202 916 144 349 171 299 732 828 269 1105 587 1014 739 1178 110 463 678 1209 578 977 358 829 271 289 181 670 659 1044 117 690 51 1108 101 282 853 1052 519 682 192 299 609 793 303 710 310 493 212 251 655 1020 127 478 547 1136 103 480 879 1002 251 640 227 903 279 1216 338 1161 206 951 60 819 268 297 1025 1155 373 1181 982 1146 64 785 4…
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: 1417 694 652 1271 323 869 138 1402 443 1150 1126 1264 856 1023 732 1161 169 923 177 536 768 1198 696 1365 430 685 129 160 229 1315 874 1166 635 834 160 414 752 1319 673 997 126 1341 769 1104 602 732 515 669 1238 1362 449 1032 615 826 457 946 677 1223 70 405 691 1336 441 1216 145 624 1118 1305 287 1256 246 433 15 1153 260 1047 253 591 229 1273 682 1258 593 894 987 1263 801 987 581 1228 848 1352 110 346 398 987 186 816 557 1218 1085 1339 704 1099 726 845 219 817 1140 1402 125 736 866 1335 827 956 993 1138 925 1366 217 587 217 788 43 450 29 1110 12 224 848 1340 198 800 517 1329 556 659 242 1004 140 294 531 539 738 892 919 1114 255 475 287 511 341 753 58 151 369 1070 1347 1376 745 869 330 1233 587 1007 398 1209 40 250 75 1205 154 1186 164 371 923 1369 479 956 1005 1189 206 403 296 753 167 792 …
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: 1254 936 4 780 952 1042 447 793 371 545 228 929 485 601 1145 1159 490 1194 672 1112 1010 1141 336 953 391 1117 40 450 1183 1254 129 138 1021 1121 1008 1157 819 829 338 1172 325 372 675 972 512 570 312 494 698 999 857 876 78 1233 794 1193 302 956 679 901 569 770 485 1085 191 436 215 1068 615 1141 412 691 382 1213 148 399 209 1053 117 842 70 1199 4 820 950 1207 597 767 531 722 418 1015 192 468 17 711 426 759 175 309 205 807 8 485 713 719 31 887 123 326 408 1169 404 1117 182 1029 338 648 547 719 570 857 47 101 112 309 258 1057 137 149 485 513 1055 1132 356 509 67 255 425 718 69 680 772 1201 356 431 157 834 562 979 270 800 83 418 162 1042 329 1190 676 1075 139 1222 1169 1215 214 463 14 487 535 686 273 926 65 323 684 1111 490 662 33 1041 1039 1114 452 807 579 652 873 1144 958 1008 66 603 285 79…
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 <= 1532; 0 <= m <= 1532.

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