🧠 题解思路（博弈 + DAG）

✅ 游戏本质

这是一个标准的 图上的博弈论问题，棋子可以视为多个“独立子游戏”的集合，最终是一个“组合游戏”。

关键在于分析：

每个位置本身是否是一个必胜态或必败态；

所有棋子的状态综合在一起，可使用**异或和（Nim和）**判定结果。

✅ 核心理论

每个位置 $i$ 可通过递归或记忆化搜索计算其 SG 值（Sprague-Grundy 数）；

如果该位置没有出边（即终点），则 SG 值为 $0$（表示必败）；

若它的出边分别指向 $v_1, v_2, \dots$，则 $SG(i) = \text{mex}(SG(v_1), SG(v_2), \dots)$；

$\text{mex}$ 表示最小不出现的非负整数。

对每次查询中棋子所在位置的 SG 值求异或和：

若异或和为 $0$，则当前状态为必败态，输出 "LOSE"；

否则为必胜态，输出 "WIN"。

✅ 实现建议

图为 DAG，建议从后往前（逆拓扑）或递归记忆化搜索计算每个位置的 SG 值；

使用 unordered_map 或 vector 存储邻接表；

每次查询直接将 $M$ 个起始位置的 SG 值做异或运算；

注意多个测试用例，读入以 0 结束。

代码实现

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 1010 
int sg[N],n,x,ans,m;
int SS[N];
int tot,to[N*N<<1],head[N],nxt[N*N<<1],cnt[N],num;
inline void add(int x,int y) {to[++tot]=y; nxt[tot]=head[x]; head[x]=tot;}
int dfs(int pos)
{
	if(sg[pos]!=-1) return sg[pos];
	bool vis[N];
	for(int i=0;i<n;i++) vis[i]=false;
	for(int i=head[pos];i;i=nxt[i]) vis[dfs(to[i])]=true;
	for(int i=0;;i++) if(!vis[i]) return sg[pos]=i;
}
int main()
{
	while(~scanf("%d",&n))
	{
		memset(sg,-1,sizeof sg);
		memset(head,0,sizeof head);
		memset(cnt,0,sizeof cnt);
		tot=0;
		for(int i=0;i<n;i++)
		{
			scanf("%d",&num);
			for(int j=1;j<=num;j++)
			{
				scanf("%d",&x);
				add(i,x); 
				cnt[x]++;
			}
		}
		for(int i=0;i<n;i++) if(!cnt[i]) sg[i]=dfs(i);
		while(scanf("%d",&m)&&m)
		{
			ans=0;
			for(int i=1;i<=m;i++)
			{
				scanf("%d",&x);
				ans^=sg[x];
			} 
			if(ans) printf("WIN\n");
			else printf("LOSE\n");
		}
	}
}