1 #include<iostream>  2 #include<cmath>  3 #include<algorithm>  4 #include<cstdio>  5 using namespace std;  6 #define maxn 760  7 int par[maxn];  8 int pos;  9 int n,m; 10 struct node 11 { 12     int x; 13     int y; 14     double w;//!可以不开方比较 15 }; 16 node e[maxn * (maxn - 1) / 2]; 17 int cmp(const node &a , const node &b) 18 { 19     return a.w < b.w; 20 }; 21 struct p 22 { 23     int x; 24     int y; 25 }po[maxn]; 26 void init() 27 { 28     for(int i = 1; i <= n+5; i++) 29         par[i] = i; 30     pos = 0; 31 } 32 int Find(int x) 33 { 34     int k,j,r; 35     r = x; 36     while(par[r] != r) 37         r = par[r]; 38     k = x; 39     while(k != r) 40     { 41         j = par[k]; 42         par[k] = r; 43         k = j; 44     } 45     return r; 46 } 47 void Merge(int x,int y) 48 { 49     int a = Find(x); 50     int b = Find(y); 51     if(a != b) 52     { 53         par[a] = par[b]; 54     } 55 } 56 void input() 57 { 58     int u,v; 59     for(int i = 1; i <= n; i++) 60         cin>>po[i].x>>po[i].y; 61     cin>>m; 62     while(m--) 63     { 64         cin>>u>>v; 65         Merge(u,v); 66     } 67 } 68  69 void make() 70 { 71     for(int i = 1; i <= n; i++) 72     { 73         for(int j = i + 1; j <= n; j++) 74         { 75             if(Find(i) != Find(j)) 76             { 77                 e[pos].x = i; 78                 e[pos].y = j; 79                 e[pos].w = (po[i].x - po[j].x) * (po[i].x - po[j].x) + (po[i].y - po[j].y) * (po[i].y - po[j].y); 80                 pos++; 81             } 82         } 83     } 84     sort(e,e+pos,cmp); 85     for(int i = 0; i < pos; i++) 86     { 87         if(Find(e[i].x) != Find(e[i].y)) 88         { 89             Merge(e[i].x,e[i].y); 90             cout<<e[i].x<<" "<<e[i].y<<endl; 91         } 92     } 93 } 94 int main() 95 { 96     freopen("input.txt","r",stdin); 97     int t; 98     cin>>t; 99     while(t--)100     {101         cin>>n;102         init();103         input();104         make();105         if(t!=0)cout<<endl; //There is a blank line between output blocks.except the last one106     }107 108     return 0;109 }