Extra Credit. Hex Game Hex Game is a board game played by two players. It is played on a graph G- (V,E) with two specified vertices s,teV. The players alternate choosing a vertex from V- s.t with those chosen by player 1 being colored blue and those chosen by player 2 being colored red. Play continues until all vertices except s and t are being colored. Player 1 wins, if and only if there is a path from s to t that passes through blue vertices Hex Game" problem Input: graph G, vertices s,t Question: Can Player 1 win? Prove, that "Hex Game" e NP. Explain each step of the proof