题目传送门
充分发扬人类智慧。
题意分析
首先考虑到 \(k=\left\lceil\dfrac m{n-1}\right\rceil\)，这应当有一些性质，因为 \(k\) 并不是一个输入的给定值。
考虑到 \(n-1\) 应当有什么用，注意到 \(n-1\) 条边会构成一棵 \(n\) 个节点的树。
因此启发我们可以考虑将边分组，维护 \(k\) 组。理想情况是前 \(k-1\) 组均有 \(n-1\) 条边，第 \(k\) 组有 \(m\bmod (n-1)\) 条边。（\(k\not\equiv0\pmod{n-1}\)）
求 \(k\) 条边不相交路径，考虑每一组维护一条路径。
因此可以维护 \(k\) 棵森林 \(T_1,T_2,\cdots,T_k\) 用于维护连通性。
具体而言，对于原图上的边 \((u,v)\)，找到最小的 \(d\) 使得 \(T_d\) 上的 \(u,v\) 不连通，就将这条边加入 \(T_d\)，从而保证了对于任意前缀，若 \((x,y)\) 在最后一棵森林中联通，则在前缀中均联通。建森林时可以通过二分找到对应森林来优化。
最后的点对即 \(T_k\) 中的任意联通点对，在 \(T_1,T_2,\cdots,T_{k-1}\) 中 DFS 找对应点对即可找到路径。
注意这样复杂度是正确的，因为 \(\mathcal O(nk)=\mathcal O(m)\)，在 \(k\) 棵森林中 DFS 是可以接受的。
但是开数组时不能直接开 \(N\times K\) 的数组，因为上界 \(N=10^5,M=2\times10^5\)。可以开一个大公共空间，或者套 vector。（但是我套三层 vector，一直报 RE……）
维护连通性可以使用并查集集。
AC 代码
时间复杂度：\(\mathcal O(m\alpha(n)\log k+m)\)。
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=2e5,M=2e5,K=M;
int n,m;
//vector<int>g[N+1];
vector<vector<vector<int> > >tree;
int k;
struct dsu{vector<int>f,size;
// int f[N+1],size[N+1];int find(int x){if(f[x]==x){return x;}return f[x]=find(f[x]);}void build(int n){f.resize(n+1);size.resize(n+1);for(int i=1;i<=n;i++){f[i]=i;size[i]=1;}}void merge(int x,int y){x=find(x),y=find(y);if(size[x]<size[y]){f[x]=y;size[y]+=size[x];}else{f[y]=x;size[x]+=size[y];}}
};
vector<dsu>dsu;
void resize(int n,int k){dsu.resize(k+1);for(int i=1;i<=k;i++){dsu[i].build(n+1);}tree.resize(k+1);for(int id=1;id<=k;id++){ tree[id].resize(n+1);for(int i=1;i<=n;i++){tree[id][i].resize(0);}}
}
void addEdge(int u,int v){/*for(int i=1;i<=k;i++){if(dsu[i].find(u)!=dsu[i].find(v)){tree[i][u].push_back(v);tree[i][v].push_back(u);dsu[i].merge(u,v);break;}}*/int l=1,r=k,ans=-1;while(l<=r){int mid=l+r>>1;if(dsu[mid].find(u)!=dsu[mid].find(v)){ans=mid;r=mid-1;}else{l=mid+1;}}if(ans!=-1){tree[ans][u].push_back(v);tree[ans][v].push_back(u);dsu[ans].merge(u,v);}
}
bool dfs(int x,int fx,int to,int id,vector<int>&ans){ans.push_back(x);if(x==to){return true;}for(int i:tree[id][x]){if(i==fx){continue;}if(dfs(i,x,to,id,ans)){return true;}}ans.pop_back();return false;
}
namespace debug{void dfs1(int x,int fx,int id){cerr<<x<<" ";for(int i:tree[id][x]){if(i==fx){continue;}dfs1(i,x,id);}}
}
int main(){/*freopen("test.in","r",stdin);freopen("test.out","w",stdout);*/ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin>>T;while(T--){cin>>n>>m;k=(m+n-2)/(n-1);resize(n,k);while(m--){int u,v;cin>>u>>v;addEdge(u,v);}bool flag=true; for(int i=1;flag&&i<=n;i++){for(int j:tree[k][i]){flag=false;cout<<i<<' '<<j<<'\n';for(int id=1;id<=k;id++){vector<int>ans;dfs(i,0,j,id,ans);cout<<ans.size()<<' ';for(int x:ans){cout<<x<<' ';}cout<<'\n';}break;}}if(flag){cout<<"-1\n";}}cout.flush();/*fclose(stdin);fclose(stdout);*/return 0;
}
/*
1
3 1
1 31 3
2 1 3
*/
/*
1
4 7
1 2
2 3
3 4
4 1
1 3
2 4
1 41 4
4 1 2 3 4
2 1 4
2 1 4
*/
/*
3
3 1
1 3
4 7
1 2
2 3
3 4
4 1
1 3
2 4
1 4
5 5
1 2
2 3
3 4
4 5
3 51 3
2 1 3
1 4
4 1 2 3 4
2 1 4
2 1 4
3 5
3 3 4 5
2 3 5
*/