
ZOJ Problem Set  3275
Description Consider the following game on an undirected graph G. There are two players, a red color player R and a blue color player B. Initially all edges of G are uncolored. The two players alternately color an uncolored edge of G with their color until all edges are colored. The goal of B is that in the end, the bluecolored edges form a connected spanning subgraph of G. A connected spanning subgraph of G is a connected subgraph that contains all the vertexes of graph G. The goal of R is to prevent B from achieving his goal. Assume that R starts the game. Suppose that both players play in the smartest way. Your task is to find out whether B will win the game. Input The input contains several test cases, ended by a line of "1 1". Output For each test case print a line which is either "YES" or "NO" indicating B will win the game or not. Sample Input 3 4 0 1 1 2 2 0 0 2 4 6 1 0 1 2 2 0 0 2 3 0 1 0 1 1 Sample Output YES NO Source: Asia 2009, Ningbo (Mainland China) 