给定一张 个点 条边的无向图，一开始所有边都没有被染色。Alice 和 Bob 在这张图上轮流操作直到所有边都被染色，Alice 先手。他们的操作为：
- Alice：选择一条没被染色的边，染上红色；
- Bob：选择一条没被染色的边，染上蓝色；
若最终被染上蓝色的边连通了整张图，那么 Bob 赢，否则 Alice 赢。
若两个人都足够聪明，求谁会赢。
，。
考虑 Jerry Wen 定理，找必要/充分条件。
对于 Bob 必胜，有一个不那么显然的必要条件：
- 能在原图中找到两棵边集不交的生成树；
考虑证明它是充要条件：
-
必要性：
设两棵生成树分别为 与 ，若某一步 Alice 选择了 中的一条边，把图分裂成了两个连通块，则 Bob 一定可以选择 中的一条跨越这两个连通块的边；Alice 选择 中的边也是同理。
-
充分性：
若没有生成树（图不连通），显然 Bob 必败。
若不存在边不交的两棵生成树但图联通，则考虑某次 Alice 操作时 Bob 的必胜条件：
图去掉所有红边，把所有蓝边复制一次后，能找到两棵边不交的生成树。
显然刚开始并不满足这个条件，若 Bob 存在一种策咯使得他某次操作后满足了这个条件（必胜策略），则由于 Alice 是先手，所以她一定能把 Bob 的策略照搬过来，使得她某一次操作后满足：
图去掉所有蓝边，把所有红边复制一次后，能找到两棵边不交的生成树。
也就是说，角色互换了。所以若 Bob 存在必胜策略，则 Alice 存在可以让红边构成一棵生成树的策略。由于不存在边相交的两颗生成树，所以 Bob 必败，与 Bob 存在必胜策略矛盾。
所以 Bob 不存在必胜策略。
Q.E.D.
观察到 比较小，所以可以直接爆搜，但是要注意剪枝。代码如下：
#include <iostream>
#include <cstdio>
#include <set>
using namespace std;
const int S=15;
struct node
{
int x,y;
}b[S*S];
int n,m;
int fa[S];
bool vis[S*S];
set<int> st;
int fnd(int x){return fa[x]==x?x:fa[x]=fnd(fa[x]);}
inline bool chk(int sta)
{
for(int i=1;i<=m;i++) vis[i]=false;
for(int i=1;i<=m;i++) if(sta>>i-1&1) vis[i]=true;
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++) if(!vis[i]) fa[fnd(b[i].x)]=fnd(b[i].y);
int r1=fnd(1);
for(int i=1;i<=n;i++) if(fnd(i)!=r1) return false;
return true;
}
bool dfs(int s1,int s2)
{
if(!chk(s1)) return false;
if(s2==(1<<n)-1) return true;
if(st.count(s1)) return false;
st.insert(s1);
for(int i=1;i<=m;i++)
{
if(s1>>i-1&1) continue;
if((s2>>b[i].x-1&1)+(s2>>b[i].y-1&1)!=1) continue;
if(dfs(s1|(1<<i-1),s2|(1<<b[i].x-1)|(1<<b[i].y-1))) return true;
}
return false;
}
inline void slove()
{
st.clear();
puts(dfs(0,1)?"YES":"NO");
}
int main()
{
while(1)
{
scanf("%d%d",&n,&m);
if(n==-1&&m==-1) break;
for(int i=1;i<=m;i++) scanf("%d%d",&b[i].x,&b[i].y);
for(int i=1;i<=m;i++) b[i].x++,b[i].y++;
slove();
}
return 0;
}