rt，本篇题解路径输出有误，自己造了几组数据确实是错误的，这里采用评论区大佬给出的hack：

输入

4 3
2 1
1 3
3 4

路径应为

2 1 3 4

输出为

1 3 4
2 1 3 4