简单的博弈论,内测阶段由于疏忽大意慢了一拍太菜了痛失一血。

其实这个逃亡的过程很简单,考虑这么一个结构:

  • 如果 ab,aca\rightarrow b, a\rightarrow c,且 b,cb,c 都可以胜利。

那么先手无论剪哪条边,后手选另外一个边走过去就赢了。

再考虑一个结构:

  • 如果 aba\rightarrow b 能赢,但是 aa 到其他所有 c1,c2,,ckc_1,c_2,\cdots,c_{k} 都赢不了。

那先手直接剪了 bb 后手就输了。

考虑完了这两个性质之后,其实这道题咱们已经思考完了:

  • 2\ge2 个必胜点,可以共同作用于一个“未知胜负”的点,使之变成“必胜”点。

那么咱们直接从最开始的 kk 个必胜点开始,建立反向边,如果某个点被 2\ge2 个必胜点“直接达到”,那么他也变成必胜点即可。

int main(){
    int T = init();
    while (T--) {
        memset(vis, 0, sizeof(vis));
        memset(du, 0, sizeof(du));
        int n = init(), m = init(), k = init();
        for (int i = 1; i <= n; ++i)
            G[i].clear();
        q[0] = 0;
        for (int i = 1; i <= k; ++i)
            q[++q[0]] = init();
        for (int i = 1; i <= k; ++i)
            vis[q[i]] = 1;
        for (int i = 1; i <= m; ++i) {
            int u = init(), v = init();
            G[u].push_back(v), G[v].push_back(u);
        }
        int nxt = 1;
        while (nxt <= q[0]) {
            int u = q[nxt++];
            for (std::vector<int>::iterator it = G[u].begin(); 
                it != G[u].end(); ++it) { // 反向遍历
                int v = *it;
                ++du[v]; // 度数 + 1
                if (du[v] >= 2 && !vis[v]) { // 如果度数 >= 2,并且它还是未知的,那么就是必胜点
                    vis[v] = 1;
                    q[++q[0]] = v; // 加入队列,继续影响后面的点
                }
            }
        }
        if (vis[1]) puts("yes");
        else puts("no");
    }
}