特判$n=2$，以下有$nge 3$
考虑两个节点的交集，分类讨论：
1.距离大于4，则交集为空
2.距离等于4，则交集大小恰好为1，即路径上中间的点
3.距离等于3，则交集大小恰好为2，即路径上的两个点（不包括端点）
4.距离等于2，则交集大小至少为3，至少包含两者路径上包括端点的3个点
5.距离等于1，由于$nge 3$，两者不都为叶子，交集大小也至少为3
所以，求出任意两个集合的交集（使用bitset），若交集大小恰好为2，即可确定这所交的这两点有边
可以发现，对于任意一条非叶子节点之间的边，都可以通过此类方法得到，假设得到了$m$条边：
1.$m=0$，任意一条边都包含叶子节点，即菊花图；
2.$m=1$，考虑是$(u,v)$，那么必然是$u$和$v$的两张菊花图，与$u$相连的点不包含与$v$相连的点，因此只需要任找一个集合删除$u$和$v$与$u$相连，其余点与$v$相连即可；
3.$mge 2$，记这$m$条边的端点所构成的集合$S$，$S_{x}={y|x=y或(x,y)在这m条边中}$
考虑对于所有输入的集合，将其与$S$求交后判断是否等于$S_{x}$，假设$T$与其相等，考虑$T$是哪一个节点所产生，有以下三种情况：
1.是一个与$x$相连的叶节点
2.是$x$自己，这还需要保证$S_{x}=S$（即到的所有点都是$S$中的叶子）
3.是在$S_{x}$中的点且不为$x$（$yin S_{x}$），这还需要保证$|S_{y}|=2$
考虑一个$|S_{x}|=2$的点，就不会出现第2和3种情况（点数大于2），那么将$T$（任选一个即可）中比$S_{x}$多的点就是与$x$相连的叶子节点（由于$x$非叶子肯定存在）
之后对于剩下的点，用同样的做法，但如果这个叶子已经出现就不插入即可
都可以用bitset优化，时间复杂度$o(frac{n^{3}}{64})$
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 1005 4 vector<pair<int,int> >E; 5 bitset<N>V,bt[N],S[N]; 6 int n,x,y,leaf[N]; 7 int main(){ 8 scanf("%d",&n); 9 if (n==2){ 10 printf("1 2"); 11 return 0; 12 } 13 for(int i=1;i<=n;i++){ 14 scanf("%d",&x); 15 for(int j=1;j<=x;j++){ 16 scanf("%d",&y); 17 bt[i][y]=1; 18 } 19 for(int j=1;j<i;j++){ 20 bt[0]=(bt[i]&bt[j]); 21 if (bt[0].count()==2){ 22 x=y=0; 23 for(int k=1;k<=n;k++) 24 if (bt[0][k]){ 25 if (!x)x=k; 26 else y=k; 27 } 28 if (S[x][y])continue; 29 V[x]=V[y]=S[x][y]=S[y][x]=1; 30 E.push_back(make_pair(x,y)); 31 } 32 } 33 } 34 if (!E.size()){ 35 for(int i=2;i<=n;i++)printf("1 %d ",i); 36 return 0; 37 } 38 if (E.size()==1){ 39 x=y=0; 40 for(int i=1;i<=n;i++) 41 if (V[i]){ 42 if (!x)x=i; 43 else y=i; 44 } 45 for(int i=1;i<=n;i++) 46 if (bt[i].count()!=n){ 47 for(int j=1;j<=n;j++) 48 if (j!=x){ 49 if (bt[i][j])printf("%d %d ",x,j); 50 else printf("%d %d ",y,j); 51 } 52 return 0; 53 } 54 } 55 for(int i=1;i<=n;i++) 56 if (V[i]){ 57 S[i][i]=1; 58 if (S[i].count()==2){ 59 for(int j=1;j<=n;j++) 60 if (!(((bt[j]&V)^S[i]).count())){ 61 for(int k=1;k<=n;k++) 62 if ((bt[j][k])&&(!V[k])){ 63 E.push_back(make_pair(i,k)); 64 leaf[k]=1; 65 } 66 break; 67 } 68 } 69 } 70 for(int i=1;i<=n;i++) 71 if ((V[i])&&(S[i].count()!=2)){ 72 for(int j=1;j<=n;j++) 73 if (!(((bt[j]&V)^S[i]).count())){ 74 for(int k=1;k<=n;k++) 75 if ((bt[j][k])&&(!V[k])&&(!leaf[k])){ 76 E.push_back(make_pair(i,k)); 77 leaf[k]=1; 78 } 79 break; 80 } 81 } 82 for(int i=0;i<E.size();i++)printf("%d %d ",E[i].first,E[i].second); 83 }