CT64301

Devi's bridges Reckoning

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Devi the measurer watches over the ferry landing of Crosswater's stores of bridges. 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 <= 2251; 0 <= m <= 2251.

Example 1:

Input: 388 1497 349 373 226 303 130 256 106 274 133 336 91 132 171 174 122 387 160 229 179 285 323 350 92 289 20 358 15 227 76 197 247 335 179 358 23 64 45 88 43 101 57 208 93 372 311 385 13 276 163 220 51 117 104 266 194 297 156 241 73 249 29 350 43 213 235 336 78 178 291 301 246 345 143 297 273 323 131 296 177 182 75 361 171 304 206 380 87 208 88 242 149 286 112 190 217 305 113 363 6 330 27 217 57 179 230 318 135 273 237 298 244 336 38 174 180 287 149 216 193 377 68 381 198 388 264 301 20 177 23 126 213 312 80 152 3 63 66 70 54 188 26 366 308 324 138 337 232 315 17 125 244 334 119 188 19 249 58 313 53 159 3 249 124 341 225 386 293 323 157 201 109 178 48 144 200 236 310 346 351 363 129 306 60 322 51 379 95 211 147 247 210 327 170 310 166 374 25 62 124 169 336 350 101 304 41 303 40 87 271 366 53 …
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: 971 2050 142 336 27 396 306 514 64 594 12 397 249 923 421 787 2 582 570 708 376 456 236 777 195 437 447 691 22 526 311 835 266 648 55 658 218 687 578 932 198 499 578 917 116 701 740 806 154 952 8 782 137 454 874 908 412 556 155 720 296 491 156 552 52 494 40 216 688 761 301 886 727 785 626 640 88 706 500 857 61 514 525 636 38 598 482 530 302 411 142 609 262 384 444 508 497 764 309 471 599 623 133 730 126 874 359 586 174 330 439 920 100 857 548 684 310 760 208 272 103 406 20 609 594 950 210 918 463 921 637 969 209 825 563 816 622 710 269 419 36 837 337 654 180 772 757 804 500 678 249 564 664 888 273 340 530 584 467 513 149 230 388 701 67 82 208 722 213 734 295 690 448 902 400 651 38 860 251 706 635 781 161 805 77 392 146 521 565 811 244 480 45 79 623 822 96 645 616 962 282 393 309 342 800 88…
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 1989 157 387 783 1388 523 1218 538 1226 561 924 266 387 512 1438 31 102 634 1065 4 464 640 739 935 1037 294 1154 38 1393 285 634 962 1445 53 724 1072 1333 812 1066 169 789 655 1390 461 879 33 552 621 840 64 718 186 1065 888 1260 106 1038 887 891 1019 1160 186 874 963 1041 432 478 850 1035 592 1174 576 1200 40 1161 609 868 985 1400 979 1361 960 1018 336 364 428 982 317 657 313 457 442 635 569 853 423 426 414 477 656 969 927 1174 521 1176 1274 1382 60 1291 475 773 1193 1297 497 919 1081 1199 832 1031 438 950 992 1168 1224 1226 824 1280 892 1335 101 1005 1261 1383 4 89 543 1042 920 1018 574 946 446 491 414 742 680 1075 980 1362 5 12 318 1147 729 750 1063 1268 114 1314 1329 1373 491 865 102 286 175 1117 518 1034 14 806 582 903 895 1411 284 1378 288 816 1118 1404 485 1252 235 811 302 1127 …
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 <= 2251; 0 <= m <= 2251.

Loading...
Test Cases:No test cases
No test cases available.
Devi's bridges Reckoning - MEDIUM Coding Problem | CodeTikki