DECOY - Decoys and Diversions

Apparently, both sides of the battle are now using some sort of cat-and-mouse tactics on the battlefield. The rules are as follows: there are two battles happening simultaneously at different fields. The armies take turns retreating one of their two units to a different location; the retreat of an army automatically causes the opposing army on the same field to follow it. The one that is cornered (that is, has nowhere to retreat on their turn) will be the one that ultimately loses the battle. Given the description of the fields, and supposing that both commanders are perfect strategists, can you decide who is going to win?

Input

The first line of input contains an integer T, the number of test cases. Each test case consists of two descriptions of the fields of the battle. A description begins with a line containing integers N (1 N 100), M (1 M 10000), the number of locations in the field and the number of roads connecting the locations, respectively. The following M lines each contain two integers u,v (1 ≤ u,v ≤ N) denoting that there is a one-way road connecting position u to the position v. The initial location of all units is at position 1 in their respective fields.

Output

For each test case, output a single line containing the result of the battle, assuming your side is the first to play. Print "I lose" if you're going to lose, "I win" if you're guaranteed to win or "Deadlock" if the battle will go on forever.

Example

Input:
3
2 1
1 2
2 1
1 2
2 2
1 2
2 1
2 1
1 2
3 2
1 2
2 3
2 1
1 2 Output: I lose
Deadlock
I win

Added by:Fernando Fonseca [ITA]
Date:2012-03-01
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2016-06-06 11:31:01 [Rampage] Blue.Mary
The input consists of self-cycles, and it should be considered as a valid move.
2012-03-01 04:56:20 Fernando Fonseca [ITA]
Fast I/O routines are highly recommended for this one. The input file is quite big.

edit: I've increased the time limit to 2s so that scanf can pass, but it's still a close call.

Last edit: 2012-03-01 05:11:51
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.