Let G = (V,E) be an (undirected) graph with weights we 0 on the edges e E. Assume you are given a minimum spanning tree T in G. Now assume that a new edge is added to G, connecting two nodes u, v V with cost w.

(a) Give an efficient algorithm to test if T remains the minimum-cost spanning tree with the new edge added to G (but not to the tree T). Make your algorithm run in time O(|E|). Can you do it in O(|V |) time? Please note any assumptions you make about what data structure is used to represent the tree T and the graph G.

(b) Suppose T is no longer the minimum-cost spanning tree. Give a linear-time algorithm (time O(|E|)) to update the tree T to the new minimum-cost spanning tree.