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 https://toph.co/p/find-the-prime-number