Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: GAME AGAIN!
Description Alice and Bob often play games together, and they always like to play new games. Now they have thought out a new game named "ESCAPE". What is the game like? This new game is played on an undirected graph, which they draw before the game, and they play game in turn. Each turn a player can choose a vertex, which is adjacent to the last vertex chosen by his opponent (in the first turn, the player can choose any vertex) and not be chosen before. The player who does not have vertex to choose loses. Suppose that Alice always plays first and they both do their best in the game. Now given the graph, can you predict who will win the game? Input The first line of the input contains a single integer T, which is the number of test cases. Then T cases follow. Each test case contains multiple lines. The first line consists of two integers N (1 <= N <= 50) and M, which indicate the number of vertices and the number of edges. In the following M line, each contains a pair of integers a and b (1 <= a, b <= N), which means that there is an edge between a and b. Output For each test case, in a single line, output "alice", if Alice will win the game, "bob", if Bob will win, otherwise output "I don't know". Sample Input 2 2 1 1 2 3 2 1 2 2 3 Sample Output bob alice Source POJ Monthly,dodo |

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

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator