8. Minimum-spanning tree algorithms are often formulated using an operation called edge contraction. To contract the edge uv, we insert a new node, redirect any edge incident to u or v (except uv) to this new node, and then delete u and v. After contraction, there may be multiple parallel edges between the new node and other nodes in the graph; we remove all but the lightest edge between any two nodes. The three classical minimum-spanning tree algorithms described in this chapter can all be expressed cleanly in terms of contraction as follows. All three algorithms start by making a clean copy G' of the input graph G and then repeatedly contract safe edges in G'; the minimum spanning tree consists of the contracted edges. (a) Figure 7.7. Contracting an edge and removing redundant parallel edges. BoruvKa: Mark the lightest edge leaving each vertex, contract all marked edges, and recurse. JARNIK: Repeatedly contract the lightest edge incident to some fixed root vertex. KRUSKAL: Repeatedly contract the lightest edge in the graph. Describe an algorithm to execute a single pass of Bortivka's contraction algorithm in O(V + E) time. The input graph is represented in an adjacency list