这也是一道非常经典的 博弈论 题目，属于 公平组合游戏 (Impartial Game) 的范畴。

这类在有向无环图（DAG）上移动棋子的游戏，通常使用 Sprague-Grundy (SG) 定理 来解决。

1. 算法核心理论

1.1 游戏分解

题目中有 $K$ 个棋子，每次玩家可以选择其中任意一个棋子移动一步。 这表明这 $K$ 个棋子的移动是相互独立的互不干扰的子游戏。 根据 SG 定理：

整个游戏的 SG 值等于所有独立子游戏 SG 值的异或和 (XOR Sum)。

1.2 SG 函数与 Mex 运算

对于有向无环图上的任意节点 $u$，其 SG 值定义为：

$$SG(u) = \text{mex}(\{SG(v) \mid u \to v \in E\})$$

• Mex (Minimum Excluded value)：集合中未出现的最小非负整数。
• 边界情况：如果一个节点 $u$ 没有出边（出度为 0），则其后继集合为空集 $\emptyset$，$\text{mex}(\emptyset) = 0$。这正好对应“无法移动者输”的必败态（P-position）。

1.3 胜负判定

设 $K$ 个棋子初始所在位置为 $p_1, p_2, \dots, p_K$。 计算整个局面的 SG 值：

$$Res = SG(p_1) \oplus SG(p_2) \oplus \dots \oplus SG(p_K) $$

• 如果 $Res \neq 0$，则先手必胜（Win）。
• 如果 $Res = 0$，则先手必败（Lose）。

2. 代码逻辑解析

这份代码完全遵循上述理论进行实现。

2.1 记忆化搜索求 SG 值

由于这是一个 DAG（有向无环图），我们可以使用 DFS + 记忆化 的方式来计算每个节点的 SG 值。

ll f[2005]; // 记忆化数组，初始化为 -1

ll sg(ll u) {
    // 1. 记忆化：如果已经计算过，直接返回
    if (f[u] != -1)
        return f[u];

    // 2. 收集所有后继节点的 SG 值
    set<ll> s;
    for (auto e : g[u])
        s.insert(sg(e)); // 递归计算子节点

    // 3. Mex 运算：找到最小的、未在集合 s 中出现的非负整数
    for (int i = 0; ; i++) {
        if (!s.count(i))
            return f[u] = i; // 记录并返回
    }
}

• set 用于自动去重和排序（虽然这里只需要去重和查找），方便判断 mex。
• 由于 $N$ 只有 2000，且是一个 DAG，递归深度有限，不会爆栈。

2.2 主处理逻辑

void solve() {
    // ... 输入建图 ...
    memset(f, -1, sizeof(f)); // 初始化 f 数组

    ll res = 0;
    for (int i = 0; i < k; i++) {
        ll x;
        cin >> x;
        res ^= sg(x); // 计算所有初始棋子 SG 值的异或和
    }

    if (res)
        cout << "win" << endl; // 异或和不为0，先手胜
    else
        cout << "lose" << endl; // 异或和为0，先手败
}

3. 复杂度分析

• 时间复杂度：
  • 计算每个节点的 $SG$ 值时，需要遍历其所有出边。
  • 由于使用了记忆化，每个节点只会被计算一次。
  • 总共有 $N$ 个节点，$M$ 条边。在计算 $Mex$ 时，使用了 std::set，对于出度为 $d$ 的节点，插入和查询的时间约为 $O(d \log d)$。
  • 总体复杂度大致为 $O(M \log N)$ 或 $O(N^2)$（最坏情况下 mex 扫描），对于 $N \le 2000, M \le 6000$ 的数据量，这是非常快的，远小于 1秒。
• 空间复杂度：$O(N+M)$，用于存储图结构和 SG 数组。

4. 总结

本题是 SG 函数的入门模板题：

1. 独立性：识别出每个棋子是独立的子游戏。
2. SG 定义：利用 DAG 的性质，通过 Mex 运算递归求解每个点的 SG 值。
3. 异或和：利用 SG 定理，通过异或和判定胜负。