思路与算法

把每颗棋子视为一个独立的公平游戏。一个局面的位置就是棋子所在节点，合法后继是该点所有出边的终点；题目没有相互阻挡规则，因此多颗棋子对应子游戏的和。定义 SG[u]=mex({SG[v] | u到v有边})，没有出边的点SG为0。

先用入度和队列求拓扑序，再倒序计算SG，保证所有后继已经求出。用长度N+1的时间戳数组标记后继SG值，以当前节点编号作为时间戳，从0开始寻找第一个没有出现的数。最后异或所有棋子初始节点的SG；非零输出win，否则输出lose。

正确性说明

DAG存在拓扑序，每条边的终点都在起点之后。倒序处理时后继值均已正确，mex定义恰好给出当前节点的SG；汇点的后继集为空，得到0，故按逆序归纳所有节点SG正确。

各棋子可移动边只由自身位置决定，每步恰改变一颗棋子，且没有平局或循环，满足公平游戏正常玩法的游戏和定理。全局SG是各子游戏SG的异或。异或为0时任意一步都会改变其中一个SG且不可能保持0；异或非零时，取异或值的最高1位，可以选择一个对应位为1的子游戏，将其SG变成更小的目标值，mex保证存在这样的后继，从而归零。因此非零恰为先手必胜，程序输出正确。

复杂度

邻接表、入度、拓扑队列、SG及标记数组的分配和初始化共O(N+M)。拓扑排序O(N+M)。标记后继遍历M条边；mex不超过出度，每个节点mex扫描至多出度加1次，合计O(N+M)，无需每个节点清空N个标记。读取并异或K颗棋子O(K)。总时间O(N+M+K)，额外空间O(N+M)。

易错点

1. 先拓扑排序再逆序计算，节点编号不代表拓扑次序。
2. 棋子抵达汇点后仍在棋盘上，但已没有合法移动，SG为0。
3. 多颗棋子可从相同节点开始，逐颗异或；两颗相同SG会抵消。
4. 不能直接异或节点编号，也不能只看出度奇偶。
5. 时间戳以不同节点编号区分，初值为-1；标记数组大小覆盖所有可能SG。输出严格使用小写win或lose。

参考代码（C++11）

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k;
    if (!(cin >> n >> m >> k))
        return 0;
    vector<vector<int>> adj(n);
    vector<int> indeg(n), order, sg(n);
    for (int i = 0, x, y; i < m; ++i) {
        cin >> x >> y;
        adj[x - 1].push_back(y - 1);
        ++indeg[y - 1];
    }
    queue<int> q;
    for (int i = 0; i < n; ++i)
        if (!indeg[i])
            q.push(i);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        order.push_back(u);
        for (int v : adj[u])
            if (!--indeg[v])
                q.push(v);
    }
    vector<int> seen(n + 1, -1);
    for (int i = n - 1; i >= 0; --i) {
        int u = order[i];
        for (int v : adj[u])
            seen[sg[v]] = u;
        while (seen[sg[u]] == u)
            ++sg[u];
    }
    int ans = 0;
    for (int i = 0, x; i < k; ++i) {
        cin >> x;
        ans ^= sg[x - 1];
    }
    cout << (ans ? "win" : "lose") << '\n';
}