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:
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 610Accepted: 170


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?


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.


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 1
1 2
3 2
1 2
2 3

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