思路：

一开始用Kruskal超时了，因为这是一个稠密图，边的数量最惨可能N^2，改用Prim。

Prim是这样的，先选一个点（这里选1）作为集合A的起始元素，然后其他点为集合B的元素，我们要做的就是每次找到B中的一个点，满足这个点到A的权值是B到A的权值中最小的，然后我们把这个点加入到A，再更新B中的点到A的最小距离。

代码：

#include<cstdio>

#include<cmath>

#include<cstring>

#include<iostream>

#include<algorithm>

#define ll long long

using namespace std;

const int N = 750+5;

int mp[N][N];   //i j的距离

int vis[N];

int dis[N];     //点到集合的最小距离

int lian[N];

int n;

struct node{

    int x,y;

}p[N];

void init(){

    for(int i = 1;i <= n;i++){  //建图

        scanf("%d%d",&p[i].x,&p[i].y);

        for(int j = 1;j <= i;j++){

            mp[i][j] = mp[j][i] = (p[i].x - p[j].x)*(p[i].x - p[j].x) + (p[i].y - p[j].y)*(p[i].y - p[j].y);

        }

    }

    int Q,a,b;

    scanf("%d",&Q);

    while(Q--){

        scanf("%d%d",&a,&b);

        mp[a][b] = mp[b][a] = 0;

    }

    memset(vis,0,sizeof(vis));  //标记该点是否连接

    for(int i = 1;i <= n;i++){

        dis[i] = mp[i][1];

        lian[i] = 1;    //初始都和1的距离最小

    }

   vis[1] = 1;

}

void Prim(){

    for(int i = 1;i < n;i++){   //找n-1条边

        int MIN = 100000005;

        int point;

        for(int j = 1;j <= n;j++){

            if(!vis[j] && dis[j] < MIN){

                MIN = dis[j];

                point = j;

            }

        }

        vis[point] = 1; //找到了

        if(mp[point][lian[point]] != 0) //为零是已经有路的

            printf("%d %d\n",point,lian[point]);    //点和他相连的点

        for(int j = 1;j <= n;j++){

            if(!vis[j] && mp[j][point] < dis[j]){

                lian[j] = point;

                dis[j] = mp[j][point];

            }

        }

    }

}

int main(){

    scanf("%d",&n);

    init();

    Prim();

    return 0;

}