如果一个点需要经过奇数次我们称其为奇点，偶数次则称其为偶点。
考虑不合法的情况，有任意两个奇点不连通，因为不经过也是经过偶数次。
那么需要处理的部分就是包含奇点的唯一一个连通块。先随意撸出一棵生成树，然后正常地 DFS 下去。显然有些结点可能不符合要求的奇偶性，对于父亲结点 \(u\) 和儿子结点 \(v\)，可以通过添加 \(u\to v\to v\) 这一步使得 \(u\) 和 \(v\) 的奇偶性均发生改变。所以我们在处理完以 \(v\) 为根的子树后（即子树除了 \(v\) 都符合要求），如果 \(v\) 不符合要求，就进行这个操作。
最后只剩下根结点，特别地，如果根结点不符合要求就去掉最后一步（不回到根结点）。
每个非根结点至多做一次操作，每次操作花费 \(2\) 步，再加上最开始 DFS 的 \(2n-1\) 步，所以序列长度至多是 \(4n-3\)，可以放心通过。