[JSOI2009]游戏

题目描述

小AA和小YY得到了《喜羊羊和灰太狼》的电影票,都很想去观看,但是电影票只有一张,于是他们用智力游戏决定胜负,赢得游戏的人可以获得电影票。 在N\*M的迷宫中有一个棋子,小AA首先任意选择棋子放置的位置。然后,小YY和小AA轮流将棋子移动到相邻的格子里。游戏的规则规定,在一次游戏中,同一个格子不能进入两次,且不能将棋子移动到某些格子中去。当玩家无法继续移动棋子时,游戏结束,最后一个移动棋子的玩家赢得了游戏。 例如下图所示的迷宫,迷宫中”.”表示棋子可以经过的格子,而”#”表示棋子不可以经过的格子: ```cpp .## ... #.# ``` 若小AA将棋子放置在(1,1),则小 AA 则无论如何都无法赢得游戏。 而若小AA将棋子放置在(3,2)或(2,3),则小AA能够赢得游戏。例如,小AA将棋子放置在(3,2),小YY只能将它移动到(2,2),此时小AA再将棋子移动到(2,3),就赢得了游戏。 小AA和小YY都是绝顶聪明的小朋友,且从不失误。小AA到底能不能赢得这场游戏,从而得到珍贵的电影票呢?

输入输出格式

输入格式


输入数据首先输入两个整数 N,M,表示了迷宫的边长。接下来 N 行,每行 M 个字符,描述了迷宫。

输出格式


若小 AA 能够赢得游戏,则输出一行"WIN",然后输出所有可以赢得游戏的起始位置,按行优先顺序输出,每行一个。 否则输出一行"LOSE"(不包含引号)。

输入输出样例

输入样例 #1

3 3
.##
...
#.#

输出样例 #1

WIN
2 3
3 2

说明

对30%的数据,有1<=n,m<=5 对100%的数据,有1<=n,m<=100