CT59706

Zoravar Counts the bridges

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Zoravar the paymaster watches over the herring shoals of Silverfin'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 <= 2264; 0 <= m <= 2264.

Example 1:

Input: 749 450 46 142 217 520 279 283 30 377 133 567 168 647 508 523 198 287 499 683 306 467 535 588 502 721 462 616 258 374 26 558 230 322 178 494 427 637 32 392 54 210 315 716 53 559 127 595 97 499 37 80 320 698 58 620 79 141 535 719 147 171 177 234 352 617 271 327 17 715 142 311 33 633 84 346 308 511 97 116 333 720 344 463 21 465 300 395 135 211 228 278 731 745 171 425 452 717 578 734 17 691 325 423 166 468 59 330 392 633 93 513 180 627 99 483 133 291 210 633 28 321 550 743 89 566 467 576 183 728 43 739 463 556 7 224 199 302 114 588 721 743 297 629 18 641 207 374 33 740 56 160 110 434 126 689 107 293 135 281 190 335 118 287 348 362 279 689 186 304 553 605 33 717 148 228 282 416 410 542 47 254 448 464 172 394 492 549 361 493 176 610 23 239 107 714 35 603 160 672 279 344 144 531 83 649 69 172 34…
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: 8 28 2 8 1 5 4 6 4 7 2 4 2 5 1 2 2 7 6 8 3 5 5 7 1 3 1 4 3 7 6 7 7 8 3 8 2 3 2 6 3 4 1 7 4 5 4 8 1 6 5 8 1 8 3 6 5 6
Output: 1 2 3 4 5 6 7 8

Example 3:

Input: 1545 2203 82 953 331 1003 566 1408 1063 1173 262 514 716 796 732 751 473 682 293 1478 630 992 513 1388 1421 1476 544 1301 763 1157 415 491 210 780 144 1074 982 1110 181 1421 515 1282 193 1200 1239 1465 1210 1423 57 157 694 1441 974 1163 355 755 38 1496 37 1401 1163 1355 756 1092 909 1337 682 815 343 586 1271 1284 1178 1279 853 866 1039 1118 1214 1250 518 1228 541 1291 226 1458 1185 1319 259 416 598 850 71 590 440 1327 850 1130 1363 1402 167 1396 522 1340 249 719 334 1188 126 1271 389 1384 169 366 273 450 75 1151 541 1254 227 833 462 894 18 1039 489 1084 410 1527 134 206 99 1475 406 770 484 1162 1098 1354 418 658 792 1429 28 630 491 803 977 1066 58 398 17 1540 759 1112 1060 1147 79 1364 275 590 894 955 70 1394 127 1410 600 1009 813 880 195 950 200 1225 386 800 791 1146 82 1110 782 1277 1384…
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 <= 2264; 0 <= m <= 2264.

Loading...
Test Cases:No test cases
No test cases available.
Zoravar Counts the bridges - MEDIUM Coding Problem | CodeTikki