考虑 $k=1$ 怎么做。欧拉回路即可。
考虑 $k=2$ 怎么做。
考虑链怎么做。走到底再走回来即可。所以一定有解。
考虑树怎么做。树可以拆成链。所以一定有解。
考虑图怎么做。图可以把点切了拆成树。所以一定有解。
考虑 $k=3$ 怎么做。
考虑链怎么做。走两步退一步再走三步，类似这样的方式走即可。所以一定有解。
考虑树怎么做。同上。所以一定有解。
考虑图怎么做。同上。所以一定有解。
考虑 $k>3$ 怎么做。
可以来回走浪费两次，偶数等价为 $k=2$，奇数等价于 $k=3$。所以一定有解。