10724

#include <iostream>
#include <map>
#include <cmath>
#include <string>
#include <vector>
#include <cstring>

#define INF 1000000000
#define EP 1e-6

using namespace std;

struct point{
	int x;
	int y;
};

struct DD{
	int i,j;
	double cst,edge;

	DD(double cst,double edge,int i,int j):cst(cst),edge(edge),i(i),j(j){
	}

	bool operator < (const DD& d )const{
		if(abs(cst-d.cst)>=EP)
		return cst<d.cst;
		if(abs(edge-d.edge)>=EP)
		return edge>d.edge;
		if(i!=d.i)
		return i>d.i;
		if(j!=d.j)
		return j>d.j;
		return false;
	}

};
vector<DD> vb;
double gr[55][55];
double road[55][55];
point P[55];

int main()
{
	int N,M;
	int a,b;
	while(cin>>N)
	{
		cin>>M;

		if(N+M==0)
		break;
		for(int i=1;i<=N;i++)
		{
			cin>>a>>b;
			P[i].x = a;
			P[i].y = b;
		}

		for(int i=1;i<=N;i++)
		{
			for(int j=1;j<=N;j++)
			{
				if(i==j)
				{
					gr[i][j]=0;
					road[i][j]=0;
				}
				else
				{
					gr[i][j]=INF;
					road[i][j]=INF;
				}

			}
		}
		for(int i=1;i<=M;i++)
		{
			cin>>a>>b;
			double d = (P[a].x-P[b].x)*(P[a].x-P[b].x)+(P[a].y-P[b].y)*(P[a].y-P[b].y);
			d = sqrt(d);

			road[a][b]=1;
			road[b][a]=1;

			gr[a][b]=d;
			gr[b][a]=d;
		}

		for(int k=1;k<=N;k++)
		{
			for(int i=1;i<=N;i++)
			{
				for(int j=1;j<=N;j++)
				{
					if(gr[i][j]>gr[i][k]+gr[k][j])
					gr[i][j] = gr[i][k]+gr[k][j];
				}
			}
		}//end of warshall

		double cost;
		double tempedge;
		DD ans(0,0,0,0);
		for(int i=1;i<=N;i++)
		{
			for(int j=1;j<=N;j++)
				{
					if(road[i][j]==1)
					continue;
					cost = 0;
					tempedge = sqrt((P[i].x-P[j].x)*(P[i].x-P[j].x) + (P[i].y-P[j].y)*(P[i].y-P[j].y));


					for(int u=1;u<=N;u++)
					{
						for(int v=1;v<=N;v++)
						{
							cost+= (gr[u][v]-
							min(gr[u][v],min(gr[u][i]+tempedge+gr[j][v],gr[v][i]+tempedge+gr[j][u])));
						}
					}

					DD dd = DD(cost,tempedge,i,j);

					ans = max(ans,dd);
				}
		}

		if(ans.cst-1>EP)
		cout<<ans.i<<" "<<ans.j<<"\n";
		else
		cout<<"No road required\n";

	}

	return 0;
}