为啥会有人觉得这是板子题啊/tuu
先对图边双连通分量缩个点，然后考虑对两条边分情况讨论：
- 两个桥边，显然答案就是经过这两个桥的路径数量之和，排序取前两大的即可。
- 一个桥边加一个非桥边，答案是经过那个桥边的路径数量，显然桥边数量 \(\ge 2\) 肯定不用考虑这种情况，桥边数量 \(=1\) 另外那条非桥边随便取答案都是一样的。
- 两个非桥边，先建一棵 DFS 树，进而继续对 DFS 树上的树边和非树边分类讨论：
- 两个非树边：显然答案是 \(0\)。
- 一个树边和一个非树边：为了使答案不是 \(0\)，这条非树边必须是唯一一条经过这条树边的非树边，这样贡献同样容易用树上差分计算得到。
- 两条树边：本题的重中之重。根据边三连通分量的理论，我们给每条非树边附随机权值，树边权值为经过它的非树边的权值的异或和，那么只有割掉两条权值相等的边答案才可能不是 \(0\)。而显然，所有权值相等的非桥边必须被同一条非树边覆盖，因此它们必然形成一条祖先后代链，因此可以对每一条链分开来处理。但是这还是不足以快速求解。考虑一个性质：我们记链上关键边从上到下分别是 \(e_1,e_2,\cdots,e_k\)，记 \(f(i,j)\) 表示选择 \(e_i,e_j\) 边以后的答案（\(i<j\)）。那么容易发现对于一个固定的 \(j\)，记 \(g_j\) 表示使得 \(f(i,j)\) 最大的 \(i\)，那么 \(g_j\) 递增，即这个模型具有决策单调性。这是因为考虑四条边 \(e_1,e_2,e_3,e_4\)，考察 \(f(1,3)+f(2,4)-f(1,4)-f(2,3)\)，必然是非负的，因为记四条边分成的五个连通块为 \(1,2,3,4,5\)，那么前者比后者多的部分是 \(1,4\) 和 \(2,5\) 的路径数量。也就是说要么 \(f(1,3)>f(2,3)\)，要么 \(f(2,4)>f(1,4)\)，交叉肯定不优于包含。这样就直接决策单调性分治即可。统计贡献线段树合并即可。
const int MAXN=5e5;
const int LOG_N=19;
const int MAXP=MAXN*60;
mt19937_64 rng(19171107);
int n,m,k,mxdep,fa[MAXN+5][LOG_N+2],fa_id[MAXN+5],dep[MAXN+5];
pii pe[MAXN+5],pk[MAXN+5];tuple<int,int,int>mx;
vector<int>vec[MAXN+5];
struct graph{
int hd[MAXN+5],to[MAXN*2+5],nxt[MAXN*2+5],ec=1;
void adde(int u,int v){to[++ec]=v;nxt[ec]=hd[u];hd[u]=ec;}
void init(){for(int i=1;i<=n;i++)hd[i]=0;ec=1;}
}G,T;
bool vis[MAXN+5];vector<int>te;
void dfs(int x,int f){
fa[x][0]=f;vis[x]=1;
for(int e=G.hd[x];e;e=G.nxt[e]){
int y=G.to[e];
if(vis[y]&&e%2==0&&y!=f)te.pb(e>>1);
else if(!vis[y]){
// printf("%d->%d\n",x,y);
dep[y]=dep[x]+1;T.adde(x,y);
fa_id[y]=e>>1;dfs(y,x);
}
}
}
int getlca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
for(int i=LOG_N;~i;i--)if(dep[x]-(1<<i)>=dep[y])x=fa[x][i];
if(x==y)return x;
for(int i=LOG_N;~i;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
int get_kanc(int x,int k){for(int i=LOG_N;~i;i--)if(k>>i&1)x=fa[x][i];return x;}
u64 key[MAXN+5],mark[MAXN+5];int cnt[MAXN+5];
void dfspush(int x){
for(int e=T.hd[x];e;e=T.nxt[e]){
int y=T.to[e];dfspush(y);
mark[x]^=mark[y];cnt[x]+=cnt[y];
}
}
struct node{int ch[2],val;}s[MAXP+5];
int rt[MAXN+5],ncnt;
void modify(int &k,int l,int r,int p,int v){
if(!k)k=++ncnt;s[k].val+=v;if(l==r)return;
int mid=l+r>>1;
if(p<=mid)modify(s[k].ch[0],l,mid,p,v);
else modify(s[k].ch[1],mid+1,r,p,v);
}
int merge(int x,int y,int l,int r){
if(!x||!y)return x+y;int mid=l+r>>1,z=++ncnt;
if(l==r)return s[z].val=s[x].val+s[y].val,z;
s[z].ch[0]=merge(s[x].ch[0],s[y].ch[0],l,mid);
s[z].ch[1]=merge(s[x].ch[1],s[y].ch[1],mid+1,r);
s[z].val=s[x].val+s[y].val;
return z;
}
int query(int k,int l,int r,int ql,int qr){
if(!k)return 0;
if(ql<=l&&r<=qr)return s[k].val;int mid=l+r>>1;
if(qr<=mid)return query(s[k].ch[0],l,mid,ql,qr);
else if(ql>mid)return query(s[k].ch[1],mid+1,r,ql,qr);
else return query(s[k].ch[0],l,mid,ql,mid)+query(s[k].ch[1],mid+1,r,mid+1,qr);
}
int calc(int x,int y){return cnt[x]+cnt[y]-2*query(rt[y],0,mxdep,0,dep[x]-1);}
void dfs_calc(int x){
for(int y:vec[x])modify(rt[x],0,mxdep,dep[y],1);
for(int e=T.hd[x];e;e=T.nxt[e]){
int y=T.to[e];dfs_calc(y);
rt[x]=merge(rt[x],rt[y],0,mxdep);
}
}
void solve(vector<int>&v,int l,int r,int pl,int pr){
if(l>r||pl>pr)return;int mid=l+r>>1;
int mxv=-1,pos=0;
for(int i=pl;i<=min(pr,mid-1);i++){
int val=calc(v[i],v[mid]);
chkmax(mx,mt(val,fa_id[v[i]],fa_id[v[mid]]));
if(val>mxv)mxv=val,pos=i;
}
solve(v,l,mid-1,pl,pos);solve(v,mid+1,r,pos,pr);
}
void work(vector<int>v){
sort(v.begin(),v.end(),[&](int x,int y){return dep[x]<dep[y];});
solve(v,0,v.size()-1,0,v.size()-1);
}
void clear(){
G.init();T.init();te.clear();mx=mt(-1,0,0);mxdep=0;
for(int i=1;i<=n;i++)mark[i]=cnt[i]=fa_id[i]=dep[i]=vis[i]=rt[i]=0,vec[i].clear();
for(int i=1;i<=m;i++)key[i]=0;
for(int i=1;i<=ncnt;i++)s[i].ch[0]=s[i].ch[1]=s[i].val=0;
ncnt=0;
}
void solve(){
scanf("%d%d",&n,&m);clear();
for(int i=1;i<=m;i++){
scanf("%d%d",&pe[i].fi,&pe[i].se);
G.adde(pe[i].fi,pe[i].se);G.adde(pe[i].se,pe[i].fi);
}
scanf("%d",&k);
for(int i=1;i<=k;i++)scanf("%d%d",&pk[i].fi,&pk[i].se);
dfs(1,0);
for(int i=1;i<=n;i++)chkmax(mxdep,dep[i]);
for(int i=1;i<=LOG_N;i++)for(int j=1;j<=n;j++)fa[j][i]=fa[fa[j][i-1]][i-1];
for(int i=1;i<=k;i++)cnt[pk[i].fi]++,cnt[pk[i].se]++,cnt[getlca(pk[i].fi,pk[i].se)]-=2;
for(int id:te)key[id]=rng(),mark[pe[id].fi]^=key[id],mark[pe[id].se]^=key[id];
dfspush(1);
for(int i=2;i<=n;i++)key[fa_id[i]]=mark[i];
vector<pii>bri;
for(int i=2;i<=n;i++)if(!key[fa_id[i]])bri.pb(mp(cnt[i],fa_id[i]));
sort(bri.begin(),bri.end(),greater<pii>());
if(bri.size()==1)chkmax(mx,mt(bri[0].fi,bri[0].se,(bri[0].se==1)?2:1));
else if(bri.size()>=2)chkmax(mx,mt(bri[0].fi+bri[1].fi,bri[0].se,bri[1].se));
map<u64,int>id;map<u64,vector<int> >pts;
for(int x:te)id[key[x]]=x;
for(int i=2;i<=n;i++)if(id.count(mark[i]))chkmax(mx,mt(cnt[i],fa_id[i],id[mark[i]]));
for(int i=1;i<=k;i++){
int u=pk[i].fi,v=pk[i].se,lc=getlca(u,v);
if(u!=lc)vec[u].pb(lc);if(v!=lc)vec[v].pb(lc);
}
for(int i=2;i<=n;i++)if(mark[i])pts[mark[i]].pb(i);
dfs_calc(1);for(auto pp:pts)work(pp.se);
if(get<0>(mx)==-1)printf("0\n%d %d\n%d %d\n",pe[1].fi,pe[1].se,pe[2].fi,pe[2].se);
else{
printf("%d\n",get<0>(mx));
printf("%d %d\n",pe[get<1>(mx)].fi,pe[get<1>(mx)].se);
printf("%d %d\n",pe[get<2>(mx)].fi,pe[get<2>(mx)].se);
}
}
int main(){
// freopen("wula.in","r",stdin);
// freopen("wula.out","w",stdout);
int qu;scanf("%d",&qu);while(qu--)solve();return 0;
}
/*
1
8 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
7 1
1 8
3 6
4
2 5
3 7
2 5
7 8
*/
/*
1
5 5
1 2
2 3
3 4
4 5
1 5
4
1 4
2 4
3 5
1 2
*/