问题1722--Araleii & Bill的冠名权争夺战 again

1722: Araleii & Bill的冠名权争夺战 again

时间限制: 1 Sec  内存限制: 128 MB
提交: 19  解决: 13
[状态] [讨论版] [提交] [命题人:]
题目描述

众所周知,WL大神有个用来卖萌的昵称叫做Araleii,此外,他还有个英文名叫做Bill。然而,随着WL大神被越来越多的人膜拜景仰,他的两个名字都想获得WL大神的冠名权,并由此展开了一场旷日持久的争夺战。

距离上一次决斗已经过去了一年,在这一年中WL大神变得越来越神,于是上一场决斗的战败者(就不告诉你是谁)想开始新的一次决斗,夺回WL大神的冠名权。

这次,他们不想再取石子了,而是直接用石子来战斗。Araleii和Bill找来n个石子,石子的战斗力分别为1、2、3、……、n(即第i个石子的战斗力为i)。理论上说,战斗力高的石子将会战胜战斗力低的石子,但是这其中有m个例外(即存在m对石子A、B,A的战斗力大于B,但是B会战胜A)。他们规定规则如下:

首先,Araleii选取一个石子,若Bill不能从剩下的石子中选出一个可以战胜该石子的石子,则Araleii获胜,否则Bill选出一个可以战胜该石子的石子。

然后(如果之前Araleii没有获胜),Araleii再从除之前两个石子外剩下的石子中选取一个石子,若可以战胜Bill的石子,则Araleii获胜,否则Bill获胜。

现在,Araleii想知道自己是否可以获胜(由于Araleii和Bill都是WL大神的名字,继承了WL大神的无上智慧,所以他们每次取石子时都会采取最优策略)。

输入

输入数据有多组。
第一行输入一个整数T,表示数据组数。
之后T组每组第一行两个整数N、M,表示石子个数和例外个数(1≤ N≤10^5,0≤M≤min(10^6,N*(N-1)/2))。
之后M行每行两个整数x、y,表示第x个石子反而可以战胜第y个石子(1≤x<y≤N)

输出

每组样例输出一行,如果Araleii获胜,输出“Bill will lose HAHA”,否则输出“I this idiot”(输出不包括引号)。

样例输入 Copy
2
1 0
3 1
1 3
样例输出 Copy
Bill will lose HAHA
Bill will lose HAHA