BD202201 洞穴
https://www.matiji.net/exam/brushquestion/1/3956/4FCAF025E79704820690062E3FDE6CA1
分析：
从小到大依次处理边 这样的好处在于如果此时没有合适的中间点 我们只需合并就好 因为后续的边一定更大 不可能是中间点
其实发现就是联通块的合并
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
void solve();
void dfs(int);
const int maxn=105;
struct node {
int val,x,y;
bool friend operator<(node aa,node bb){
return aa.val>bb.val;
}
}a[maxn];
int n,cnt,fa[maxn];
priority_queue<node>Q;
int find(int x){
if(x!=fa[x])return fa[x]=find(fa[x]);
return x;
}
pair<int,int> res[maxn];
int main(){
int T;cin>>T;
while(T--)solve();
return 0;
}
void solve(){
cin>>n;
cnt=0;
for(int i=1;i<=n;i++)fa[i]=i;
for(int xx,i=1;i<=n;i++)
for(int j=1;j<=n;j++){
cin>>xx;
if(i<j){
node t;
t.x=i,t.y=j,t.val=xx;
Q.push(t);
}
}
while(!Q.empty()){
node t=Q.top();
Q.pop();
int fx=find(t.x),fy=find(t.y);
if(fx!=fy){
fa[fx]=fy;
res[++cnt]={t.x,t.y};
}
}
sort(res+1,res+1+cnt);
cout<<cnt<<endl;
for(int i=1;i<=cnt;i++)
cout<<res[i].first<<" "<<res[i].second<<endl;
}