CT58758

Bhanu Counts the bridges

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Bhanu runs the granary at the mulberry rows of Silkmead. Today the books show a list of bridges, and the numbers must be worked out before sundown. 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 <= 1754; 0 <= m <= 1754.

Example 1:

Input: 94 1079 72 83 27 38 15 50 31 41 41 84 12 22 25 34 42 59 4 14 30 79 4 17 16 33 8 47 32 78 23 39 87 91 86 90 33 34 5 44 2 53 29 94 15 55 68 73 49 79 50 82 44 68 31 39 65 74 41 56 47 78 22 66 25 65 13 38 35 45 15 38 11 94 29 65 78 91 12 20 16 90 45 51 29 84 6 44 63 90 15 77 71 89 75 90 23 51 54 88 40 50 4 67 50 57 3 55 56 57 73 94 27 90 37 79 4 9 65 89 59 69 4 86 20 47 13 28 49 80 5 31 36 91 62 66 42 82 78 85 57 68 19 81 52 91 42 90 80 86 3 72 19 91 1 71 31 78 33 77 47 57 59 92 52 57 6 74 10 41 53 68 20 45 29 75 24 57 19 64 46 72 32 64 31 56 51 94 26 39 48 87 36 84 13 73 5 58 19 69 64 71 17 32 3 42 25 39 13 25 21 23 6 40 60 85 32 46 62 94 27 77 69 82 14 41 40 90 34 50 33 56 18 58 19 26 10 19 25 68 8 51 2 43 67 88 32 82 46 85 5 78 14 63 17 71 10 80 35 94 45 61 83 88 17 66 17 50 5 89 34 73 16 2…
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

Example 2:

Input: 1498 766 303 1049 408 1410 384 1414 150 1229 466 994 202 1086 705 775 530 730 1036 1487 1434 1495 538 1396 694 926 627 1108 350 405 128 680 772 856 91 1094 862 1194 160 171 328 878 76 347 1435 1485 838 1070 157 569 247 1431 295 993 116 455 1295 1490 219 953 190 430 149 1002 1227 1336 176 504 107 1140 348 1062 908 1045 814 1082 326 912 425 1288 335 1044 52 763 451 1326 168 1365 277 352 169 812 564 1422 183 1495 410 501 1152 1477 766 1041 28 433 830 1489 204 445 152 959 372 402 407 1096 65 1426 1312 1332 1134 1154 561 1233 7 216 204 893 211 1056 289 1313 61 346 453 1434 498 1419 740 1338 586 857 347 1059 210 437 247 440 1061 1293 772 1041 170 593 143 359 275 507 152 1147 12 975 986 1279 835 1419 998 1304 44 735 379 551 1096 1403 1289 1407 63 965 210 976 619 1276 77 1339 100 773 57 252 665 81…
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: 1517 552 312 903 678 800 186 1103 658 1313 127 545 1018 1274 408 435 654 1449 971 1121 754 1206 237 260 442 1093 584 1399 124 938 395 494 381 878 73 1176 8 1458 226 1057 772 1374 50 972 1303 1373 407 561 8 611 1151 1461 583 700 1094 1510 108 240 910 1217 1300 1360 18 838 676 1357 719 754 1123 1261 195 1052 735 1398 458 617 610 870 1158 1455 844 1439 34 984 493 1300 827 1265 282 1460 46 1065 1132 1265 659 1261 627 750 407 881 178 1083 328 1437 473 504 465 1445 63 848 818 1040 696 1126 687 809 646 1208 94 302 622 913 1043 1191 1445 1500 320 321 253 1464 437 811 770 975 457 837 204 1514 63 571 729 1229 1375 1490 261 664 403 716 209 989 316 940 530 1196 49 1396 664 854 338 944 690 1430 643 873 19 261 726 1024 1240 1508 350 1179 363 806 343 375 548 1080 324 1396 615 1196 684 791 584 1173 110 13…
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 <= 1754; 0 <= m <= 1754.

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