CT41693

The Link Budget of Palemere

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

It is audit day at the salt flats of Palemere. Ishaan spreads the marks records across the table and picks up a sharp pencil. Task: n isolated nodes are joined by m edges (some may be redundant). Print the minimum number of additional edges needed to make the graph connected. Input format: First line: n and m. Next m lines: u v. Output format: Print the number of extra edges needed. Constraints: 1 <= n <= 4000; 0 <= m <= 4000.

Example 1:

Input: 10000 2886 2812 4331 4975 9020 5215 9470 2564 5440 4401 6765 1021 5723 7559 7723 3548 5581 1365 5902 409 434 808 9267 2878 6529 532 1734 2703 9375 4791 7693 790 3276 2334 7421 78 8161 2437 3597 6298 9792 2632 4829 347 1940 1591 2858 3059 7677 6000 8908 3064 4394 4430 9290 4770 8470 1233 1859 2646 8054 4909 8708 2299 6674 2188 5712 5718 7429 227 2437 2106 7558 1964 3423 1147 3597 3799 5978 3441 7301 435 9565 4576 7444 3665 5305 7143 8199 2307 3436 1430 3042 9048 9245 1264 3187 2198 2631 1745 3032 5812 6101 2009 6690 637 1790 5320 5898 8304 8421 1993 3885 9846 9936 2104 4918 4112 8190 873 8194 353 7794 5022 9554 9 19 3048 7208 1742 9920 1819 4365 4164 9615 2643 5220 6238 9829 947 4062 6190 7681 1802 6492 3224 6889 7353 9374 3701 8863 3131 5731 2290 2795 4270 6395 4499 4599 2814 8866 4906 545…
Output: 7113

Example 2:

Input: 10 16 3 8 4 5 4 9 1 2 3 6 1 10 5 6 1 5 4 6 6 9 7 9 7 8 9 10 6 7 2 7 5 10
Output: 0

Example 3:

Input: 10000 600 4062 5948 662 6996 380 8363 6470 9657 566 2493 3608 8651 3597 4406 5704 8300 4488 9047 3253 5314 386 6488 557 8151 4283 5669 3228 9025 4280 8785 8161 9108 2960 5156 3909 4056 1897 8793 6924 9336 4093 5548 8364 9420 714 8251 3597 8935 2307 3763 2875 5370 1870 5629 6769 8839 7271 9755 6765 8589 2880 8124 961 9732 1583 2447 1659 6776 3496 9825 8075 8359 3538 9926 7873 8028 2139 8852 2340 3647 2416 9216 2881 9234 2238 4226 3536 6746 6431 8133 1215 1912 70 2474 7221 7375 8254 9204 7002 7609 4385 4557 4719 5978 7448 8083 1794 2516 1617 4087 6547 8766 2114 9306 7601 8079 1623 9330 7706 8838 3015 5856 6599 7566 1151 8001 4904 9441 6996 8880 2800 7720 366 3479 1985 4137 5241 5792 3624 8489 7141 9447 2476 5854 3761 9534 2442 7678 2517 6877 234 4483 5121 6259 3667 3785 3734 8074 5715 8902 5…
Output: 9399

Constraints:

1 <= n <= 4000; 0 <= m <= 4000.

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