#P2425. A Chess Game

A Chess Game

题目描述

我们来设计一种新的棋类游戏。

游戏中共有 NN 个位置可以放置 MM 个棋子,多个棋子可以处于同一个位置。所有位置构成一个有向无环图(DAG),也就是说,有些位置之间存在有向边连接,并且整个图中不存在环。

你和我轮流移动棋子,每次轮到一个人,只能移动一颗棋子,从它当前所在的位置,走一条有向边到达某个相邻的出边位置。

游戏一直进行,直到某个玩家无法移动任何棋子为止——那个人就输掉比赛。

如果你不能移动,你就输;如果我不能移动,我就把棋盘打乱,然后再来一次。

你敢挑战我吗?那就写个程序来看看你能否获胜吧!

输入格式

输入包含多个测试用例,每个测试用例的结构如下:

第一行一个整数 NN,表示位置的总数(1N10001 \leq N \leq 1000);

接下来 NN 行,每行描述一个位置 ii0i<N0 \leq i < N)的出边情况:

每行首先是一个整数 XiX_i(该点的出边数量),

接下来 XiX_i 个整数,表示 ii 的所有出边指向的位置编号;

然后是若干个“查询”,每个查询为一行,表示当前 MM 个棋子的初始位置:

行以一个整数 MM 开头(1M101 \leq M \leq 10),

后面跟着 MM 个整数,表示每个棋子的初始位置;

一个只含 00 的行表示当前测试用例结束。

输入最后以 N=0N = 0 的一组测试用例表示所有输入结束。

输出格式

对于每一个查询,输出一行结果:

若先手玩家必胜,输出字符串 "WIN";

若后手玩家有必胜策略,输出字符串 "LOSE"。

4
2 1 2
0
1 3
0
1 0
2 0 2
0

4
1 1
1 2
0
0
2 0 1
2 1 1
3 0 1 3
0
WIN
WIN
WIN
LOSE
WIN