比较有意思的小清新题。
第一步是时光倒流，看成是每次经过一条未被访问过的边才染色。
奇偶相关容易想到二分图。发现若有一个黑白交替的奇环（即从一个点开始遍历完整个环得到的颜色序列是黑白交替地），那我们可以先染完这个环。又因为它是奇环，所以我们遍历一遍这个环就可以切换颜色。这样一定能把全部边都染上对应的颜色。所以若有一个黑白交替的奇环答案就是 Yes。
这部分的判定可以先枚举一个点 \(u\) 然后 bfs，设 \(f_{v, 0/1}\) 表示能否经过偶数 / 奇数条黑白交替的边到达点 \(v\)。那么存在一个包含 \(u\) 的黑白交替的奇环等价于存在 \(u\) 的一条出边 \((u, v)\) 使得 \(f_{v, 0} = 1\)。
那么其他情况我们就无法切换颜色，也就是说每次到一个点，它出去时给边染的颜色是固定的。根据这个我们也可以给点染色，一个点的颜色代表它走一步时会给对应的出边染什么颜色。
因为每个点的颜色必须是唯一的，所以此时若图不是二分图就无解。否则我们枚举一个出发点 \(u\) 和 \(u\) 的颜色，判断能不能遍历完整个图（如果一个点的出边和这个点颜色相同就可以继续遍历下去）。如果存在一个点 \(u\) 和 \(u\) 的颜色，使得能遍历完整个图，答案就是 Yes，否则就是 No。
时间复杂度 \(O(nm)\)。