看到图论的路径构造题，可以尝试 DFS 树。
建完树，就变成了 $k$ 条路径覆盖树的问题。
我们注意到 $\frac{2n}{k}$ 这个限制很奇怪，$\frac{2n}{k}\times k=2n$，也就是说我们要树上的每条边走两次，两次自然是一次进去子树一次回来。
如何用点表示子树？自然是 DFS 序。但是因为要往回走，所以回来的时候还要再记录一下，也就是欧拉序。把欧拉序均匀的分成 $k$ 段给每个人就行了。
为了实现方便，代码中没有均分，而是尽量先让一个人走满上界然后再给下一个人走。
#include<iostream>
#include<vector>
using namespace std;
const int N=2e5+5;
struct edge
{
int to,nxt;
}e[N*2];
int n,m,k,cnt,tot,dfn[N*2],v[N],head[N];
vector<int> ans[N];
void add(int x,int y)
{
e[++cnt].to=y;
e[cnt].nxt=head[x];
head[x]=cnt;
}
void dfs(int now)
{
dfn[++tot]=now;
v[now]=1;
for(int i=head[now];i;i=e[i].nxt)
{
if(!v[e[i].to]) dfs(e[i].to),dfn[++tot]=now;
}
}
int main()
{
cin>>n>>m>>k;
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
add(x,y);add(y,x);
}
dfs(1);
int len=2*n/k+((2*n)%k!=0);
for(int i=1;i<=tot;i++)
ans[i/len+1].push_back(dfn[i]);
for(int i=1;i<=k;i++)
{
if(ans[i].empty())
ans[i].push_back(1);
cout<<ans[i].size()<<" ";
for(int j=0;j<ans[i].size();j++)
cout<<ans[i][j]<<" ";
cout<<"\n";
}
return 0;
}
