Find the Prime Number

You are given a bidirectional graph with N vertices and M edges. All edges are painted into either red or black. Your job is to find a spanning tree with some prime number of red edges.

This is a companion discussion topic for the original entry at