Let $G = (V, E)$ be a connected graph which has a perfect matching. Devise (and prove its correctness) an $O(|V | + |E|)$ time complexity algorithm that constructs a spanning tree $T$ of $G$ such that $V (T)$ admits a bipartition in two stable sets of maximum cardinality in $T$.
I encountered this problem in a book I have about graphs theory, and I struggled for a couple of hours already. The problem is I do not have a starting point for it. Any kind of help would be appreciated.
Modify BSF so that whenever a vertex is labeled as visited the matched vertex under the perfect matching is also labeled. The resulting tree will have the desired property.