Discussion #1785 - Problem #6582

先强化一下这个题目的条件，要求每条边都在恰好一条路径中。

发现每条路径都需要满足长度为偶数的限制不是很好做，考虑 dfs 出一个生成树，将形如 $(u,v),(v,w)$ 的两条边缩成新图上的 $(u,w)$ 一条边，这样新图的一条边就对应了原图的两条边，天然满足了路径长度为偶数的限制。

那么接下来只需要建立一个超级源点 $S$，将 $S$ 对新图中所有度数为奇数的点连边，跑一下欧拉回路即可得到构造方案（所有点度数都为偶数时必定有解）。