Build the network instead of removing extra edges.

Suppose you have the final graph (after removing extra edges). Consider the subgraph with only the edges that Alice can traverse. What structure does this subgraph have? How many edges are there?

Use disjoint set union data structure for both Alice and Bob.

Always use Type 3 edges first, and connect the still isolated ones using other edges.