CT37990

Last beacons of Yash

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Yash found an old ledger of beacons in the kitchen attic at the fox den of Rustwood. The margin notes pose a precise question. 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: 10 12 1 5 2 6 5 6 8 9 4 6 2 8 3 9 7 9 2 7 4 10 3 8 4 5
Output: 0

Example 2:

Input: 100 1904 25 38 22 98 33 50 1 92 64 89 6 49 52 78 44 55 72 84 37 63 39 72 40 70 42 52 10 26 13 84 33 62 32 58 17 39 5 76 16 61 18 95 22 58 39 56 2 42 72 99 5 74 58 66 28 86 76 93 46 56 27 91 51 73 1 78 11 67 8 94 2 67 17 76 44 57 7 47 30 87 71 81 12 84 4 74 25 50 49 59 22 54 28 47 4 59 16 64 28 66 40 89 8 34 40 47 32 73 52 87 68 78 33 69 16 82 15 71 90 93 36 96 6 69 38 85 11 76 14 25 40 69 6 66 9 73 20 94 14 79 14 53 88 97 13 45 7 17 9 95 61 98 10 46 28 88 1 81 63 78 13 59 50 62 31 73 35 99 29 87 21 94 19 94 38 47 11 30 55 67 58 67 1 29 76 95 37 52 27 47 32 90 7 87 20 24 51 54 26 42 2 48 31 52 11 86 68 72 28 59 6 26 28 38 46 67 36 42 35 42 78 84 9 20 10 14 1 2 17 28 51 84 3 61 34 96 29 51 44 100 22 72 54 58 80 95 35 76 40 80 1 23 6 43 47 58 17 19 25 65 35 90 26 94 6 15 24 61 42 77 14 97 50 …
Output: 0

Example 3:

Input: 100 2791 11 77 23 55 21 89 34 37 1 79 15 88 67 73 37 73 72 98 12 60 41 91 35 96 18 100 59 81 9 14 60 62 2 7 18 19 43 99 45 76 17 90 26 60 55 70 58 87 22 96 3 6 40 100 40 71 45 71 25 47 23 86 37 77 34 95 13 14 33 100 11 73 79 82 75 91 39 95 15 49 20 58 3 69 1 18 36 68 66 86 24 66 67 100 20 48 7 47 60 79 36 74 62 70 64 75 47 91 9 61 65 66 42 88 16 81 42 92 58 66 10 79 7 76 19 78 58 73 15 55 15 65 35 82 1 58 17 22 19 41 4 82 22 67 17 19 36 73 50 82 23 59 11 57 1 30 22 43 26 37 39 82 43 95 46 50 34 54 64 76 1 22 12 44 43 98 4 74 48 77 73 85 16 70 7 71 27 86 53 79 18 41 28 96 56 59 51 57 35 64 34 59 21 29 16 76 11 38 28 46 38 44 41 90 28 32 53 75 24 70 8 30 51 76 24 32 3 42 39 90 20 26 17 62 14 75 1 55 3 16 34 52 29 79 27 42 42 56 47 51 19 49 16 30 72 95 15 59 33 54 60 87 77 89 58 95 57 66 50 6…
Output: 0

Constraints:

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

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