小 AA 和小 YY 得到了《喜羊羊和灰太狼》的电影票,都很想去观看,但是电影票只有一张,于是他们用智力游戏决定胜负,赢得游戏的人可以获得电影票。
在 N \times M 的迷宫中有一个棋子,小 AA 首先任意选择棋子放置的位置。然后,小 YY 和小 AA 轮流将棋子移动到相邻的格子里。游戏的规则规定,在一次游戏中,同一个格子不能进入两次,且不能将棋子移动到某些格子中去。当玩家无法继续移动棋子时,游戏结束,最后一个移动棋子的玩家赢得了游戏。
例如下图所示的迷宫,迷宫中 .
表示棋子可以经过的格子,而 #
表示棋子不可以经过的格子:
.##
...
#.#
若小 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
。
3 3 .## ... #.#
WIN 2 3 3 2
对于100\%的数据,有1≤n,m≤100。
对于30\%的数据,有1≤n,m≤5。