题解

思路

考虑一条能够返回起点的路线中第一个被第二次访问的顶点。

做法

在到达它之前，每个顶点都只访问过一次，所以沿途经过的边在初始状态下都连接异色顶点；最后回到已访问顶点时，移动目标的颜色已经翻转过，而移动来源仍为初始颜色，因此最后这条边在初始状态下连接同色顶点。反过来，若一条同色边的两端能通过若干条异色边连通，就可以沿这条异色路径移动，再借同色边闭合路线。

因此先把所有异色边的两端用并查集合并，再检查每条同色边：若它的两个端点已经属于同一连通块，答案为 Yes；否则为 No。

复杂度

时间复杂度为 $O((N+M)\alpha(N))$，空间复杂度为 $O(N+M)$。