Mike is tired of snooping on hardworking Americans who pay his salary1. Despite the generous benefits, working for the federal government... is not that great. Unlimited and unchecked access to everyone's data sounds fun, but he'd rather be properly compensated for his service. Instead, Mike wants to sell out and join Seb on the fruit farm2 where they totally believe in privacy. Totally.

While attending WWDC23 and witnessing the unveiling of the Vision Pro3, Mike met a Notre Dame Computer Science and Engineering alumna who suggested that maybe he should consider joining the cult^H^H^H^H company4. After some consideration (very brief), Mike decides he wants to give it a shot. As a long time fruit farm consumer and advocate, he would feel at home at the company, and would get a strong sense of belonging and fulfillment, which is really what he is currently missing in his current position.

Inspired and fueled by the magic of the fruit farm, Mike decides to buckle down and grind some programming challenges (without GPT and Co-Pilot!) in order to ace his future technical interviews. In searching for some more exotic and off-beat programming problems, he comes across the DailyProgrammer subreddit which posts different programming puzzles for users to try out and share.

After some surveying, he comes across a challenging problem about minimum spanning trees:

Given an undirected graph in the form of an adjaceny matrix, determine the weight of the minimum spanning tree and its associated edges.

For instance, in Graph 0 above, the minimum spanning tree would have a total edge weight of 10 and consist of the following edges:

(A, C)
(B, C)
(C, E)
(D, E)
(D, F)

You will be given a series of graphs specified by a distance matrix. You are to compute the minimum spanning tree and output the total edge weight of the tree and the edges in the tree.

Unfortunately, his data structures knowledge is a bit rusty and this is a bit of a struggle for him... likewise, the ongoing Reddit Blackout is making it difficult for him to access information on Reddit, so he decides to ask for your help once again on coming up a solution for the problem described above.

#### Inspiration¶

This problem is inspired by Challenge #152 [Hard] Minimum Spanning Tree from the DailyProgrammer subreddit.

## Input¶

You will be given a series of undirected graphs from in the following format:

NVERTICES
-1 -1 ...
-1 -1 ...

The first line specifies the number of vertices in the undirected graph, which will be between 1 and 26 (inclusive). This is followed by a distance matrix with each row separated by newlines and each column separated by spaces:

• -1 is used to denote there is no edge between a pair of vertices.

• The vertices are assumed to be named A, B, C, D and so on, with the matrix representing them in that order (left-to-right and top-to-bottom).

### Example Input¶

Here is an example of the input for the problem (corresponding to Graph 0 and Graph 1 in the diagram above):

6
-1  4  2 -1 -1 -1
4 -1  1  8 -1 -1
2  1 -1 -1  4 -1
-1  8 -1 -1  2  1
-1 -1  4  2 -1  7
-1 -1 -1  1  7 -1
5
-1  2  6 -1 -1
2 -1  4  1 -1
6  4 -1 -1  1
-1  1 -1 -1  1
-1 -1  1  1 -1

## Output¶

For each undirected graph, you are to print out the total weight of the minimum spanning tree, and then the edges of the minimum spanning tree represented by the two vertices such as AB in lexicographical order.

### Example Output¶

For example, given the input above, you should output the following:

10
AC
BC
CE
DE
DF

5
AB
BD
CE
DE

Note: You must put an empty line between the outputs of each graph.

#### Algorithmic Complexity¶

For each input test case, your solution should have the following targets:

 Time Complexity O(VlogV), where V is the number of vertices in the graph. Space Complexity O(V+E), where V is the number of vertices and E is the number of edges in the graph.

Your solution may be below the targets, but it should not exceed them.

## Submission¶

\$ cd path/to/cse-30872-su24-assignments     # Go to assignments repository
\$ git checkout master                       # Make sure we are on master
\$ git pull --rebase                         # Pull any changes from GitHub

\$ git checkout -b challenge18               # Create and checkout challenge18 branch

\$ \$EDITOR challenge18/program.py            # Edit your code

\$ git commit -m "challenge18: done"         # Commit your changes

\$ git push -u origin challenge18            # Send changes to GitHub

To check your code, you can use the .scripts/check.py script or curl:

\$ .scripts/check.py
Checking challenge18 program.py ...
Result Success
Time 0.03
Score 6.00 / 6.00

\$ curl -F source=@challenge18/program.py https://dredd.h4x0r.space/code/cse-30872-su24/challenge18
{"result": "Success", "score": 6, "time": 0.03165841102600098, "value": 6, "status": 0}

#### Pull Request¶

Once you have committed your work and pushed it to GitHub, remember to create a pull request and assign it to the instructor.

1. It's well know that the US is spying on its own citizens

2. At this point... who isn't?