Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Graph Game
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 333Accepted: 60


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 blue-colored 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.


The input contains several test cases, ended by a line of `-1 -1'.

Each test case begins with a line of two integers n (1 <= n <= 10) and m (0 <= m <= 30), indicating the number of vertexes and edges in the graph. All vertexes are numbered from 0 to n - 1.

Then m lines follow. Each line contains two integers p and q (0 <= p, q < n), indicating there is an edge between vertex p and vertex q.

It is possible that the graph contains more than one edge between two vertexes and self-loops.


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



[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator