双重欧拉回路

度数为 $1$ 的顶点会迫使游走沿刚经过的边立即返回，因此无解。反之，如果所有顶点的度数都至少为 $2$，则一定有解。图中可以有桥。

将每条边复制一份，用 Hierholzer 算法构造欧拉回路。把连续经过同一条原始边称为掉头，最后一条边与第一条边的连接处也要检查。

选取一次掉头 $u\to v\to u$。由于 $v$ 的度数至少为 $2$，回路中还有另一次访问 $x\to v\to y$。边 $uv$ 的两次使用都已包含在选中的掉头中，所以 $x\neq u$ 且 $y\neq u$。允许 $x=y$。

反转两次访问之间的区间 $v\to u\to\cdots\to x\to v$。两端变成 $u\to v\to x$ 和 $u\to$，都不是掉头。区间内部是否掉头不变，各边的使用次数和游走的闭合性也不变。因此掉头次数至少减少 ，且不会产生新的掉头。

初始掉头次数至多为 $M$。每次查找并反转区间需要 $O(M)$ 时间，因此总时间复杂度为 $O(N+M^2)$，空间复杂度为 $O(N+M)$。所有测试用例的时间不超过 。

子任务 1 用三进制记录每条边的使用次数，并对当前顶点、上一条边及三进制状态进行记忆化搜索。可以固定先沿一个方向经过输入中的第一条边，因为任何合法回路都能通过循环移位及必要时反转满足该要求。时间复杂度为 $O(NM^2 3^M)$，空间复杂度为 $O(NM3^M)$。、 时可以通过。

子任务 2 的图只能是路径或环。路径无解，环沿同一方向走两圈即可，时间和空间复杂度均为 $O(N+M)$。子任务 3 使用上述反转算法。

Solution written by GPT