题目等价于去掉两条边，使得剩下的图连通，且所有点度数都为偶数。
首先特判掉图一开始就不连通的情况。
求出dfs生成树，对于每条非树边随机一个权值，每条树边的权值为所有经过它的非树边权值的异或和。
那么剩下的图连通等价于两条边权值非$0$，且两条边的权值不等。
如果有$2$个奇点，那么两条边有公共点，枚举公共点判断即可。
否则只能是$4$个奇点，分类讨论判断所有连边方式即可。
时间复杂度$O(n+m)$。
#include<cstdio>
#define N 200010
int Case,n,m,i,x,y,g[N],v[N<<1],nxt[N<<1],ed,d[N],vis[N],dfn,f[N],q[N],cnt,ansx,ansy;
unsigned long long seed,h[N],tag[N];
inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}
inline void add(int x,int y){d[x]^=1;v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
void dfs(int x,int y){
vis[x]=++dfn;
for(int i=g[x];i;i=nxt[i]){
int u=v[i];
if(u==y)continue;
if(!vis[u])f[u]=i>>1,dfs(u,x);
else if(vis[u]<vis[x]){
h[i>>1]=seed=seed*233+17;
tag[x]^=seed,tag[u]^=seed;
}
}
}
void dfs2(int x,int y){
vis[x]=++dfn;
for(int i=g[x];i;i=nxt[i]){
int u=v[i];
if(u==y)continue;
if(!vis[u])dfs2(u,x),tag[x]^=tag[u];
}
if(x>1)h[f[x]]^=tag[x];
}
inline int get(int x,int y){
for(int i=g[x];i;i=nxt[i])if(v[i]==y)return i>>1;
return 0;
}
inline void up(int x,int y){
if(!x||!y)return;
if(!h[x]||!h[y]||h[x]==h[y])return;
if(x>y){int z=x;x=y;y=z;}
if(x<ansx)ansx=x,ansy=y;else if(x==ansx&&y<ansy)ansy=y;
}
bool solve(){
dfn=cnt=seed=0;
for(i=1;i<=n;i++)g[i]=d[i]=vis[i]=f[i]=tag[i]=0;
for(i=1;i<=m;i++)h[i]=0;
for(ed=i=1;i<=m;i++)read(x),read(y),add(x,y),add(y,x);
for(i=1;i<=n;i++)if(d[i])q[++cnt]=i;
if(cnt!=2&&cnt!=4)return 0;
dfs(1,0);
for(i=1;i<=n;i++)if(!vis[i])return 0;
for(dfn=0,i=1;i<=n;i++)vis[i]=0;
dfs2(1,0);
ansx=N;
if(cnt==4){
up(get(q[1],q[2]),get(q[3],q[4]));
up(get(q[1],q[3]),get(q[2],q[4]));
up(get(q[1],q[4]),get(q[2],q[3]));
}else for(i=1;i<=n;i++)if(!d[i])up(get(i,q[1]),get(i,q[2]));
if(ansx<N)return printf("YES\n%d %d\n",ansx,ansy),1;
return 0;
}
int main(){
while(~scanf("%d%d",&n,&m)){
printf("Case %d: ",++Case);
if(!solve())puts("NO");
}
return 0;
}