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