algorithm - How to solve the following graph game -

Please consider the following game an unrestricted graph. There are two players, a player of red and a blue player B. Initially, all the edges of G are painted until all the edges are dyed, by both the players alternately on the countless edges of G Give color. The goal of B. is that, in the end, the edges of blue colonies form a connected span of the G-epithet. The attached epitope of the G is a connected subgraph that contains all the headings of the graphs. R's goal is to prevent B by achieving its goal

Let's assume that the R game starts. Suppose both players play in the best way.

Input: The case of each trial starts with the line of two integers (1 <= n & lt; = 10) and m (0 <= M & lt; = 30) , Shows the number of sequences and edges in the graph. All vertexes are counted from 0 to n-1. Then follow the M lines. Each row has two integers P and q (0 and lt; = p, q & lt; n), which indicates that the edge between the peak P and the vein q is.

Output: Print a line for each test case that is either "yes" or "no", which indicates B, will win the game or not.

Example:

3 4

1 2

2

0 2

< P> Output: Yes

My thoughts: If we can find two decomposed spanning trees of the graph, then player B wins the game. Otherwise, A win, 'Two split spanning trees' means that the sets of two trees are separated.

I wonder if you can prove my point of view or prove wrong.

your idea is correct

If you use the "Connectivity Game "Or" Maker Breaker Games ", then you should get some more interesting problems and algorithms.