1. (30 pts.) Another MST VariantSuppose we are given a weighted connected undirected graph where every vertex is colored either red or black, and we want to find a spanning tree where no edge is between two vertices of the same color (we call such an edge monochromatic). Describe an algorithm which either finds such a tree of least total weight or determines that none exists (e.g. if all vertices have the same color). Give a short argument for why your algorithm is correct.