/* Dijkstra's Algorithm */

#include<cmath>
#include<queue>
#include<vector>
#include<iostream>

#define	mp	make_pair
#define	pb	push_back

using namespace std;

typedef	vector<int>			vi;
typedef	pair<double,int>	pdi;

const int inf=1000000000;
int n,id[1000],x[1000],y[1000];
double adj[1000][1000];

bool Dijkstra(int s,int g,int *path)
{
	double d[1000];
	bool visited[1000];
	for(int i=0;i<n;i++)	d[i]=inf,visited[i]=false;
	d[s]=0;
	priority_queue<pdi> pq;	pq.push(mp(0,s));
	while(!pq.empty()){
		pdi a=pq.top();	pq.pop();
		double dis=-a.first;
		int u=a.second;
		if(visited[u])	continue;
		if(u==g)	return true;
		visited[u]=true;
		for(int v=0;v<n;v++){
			if(visited[v])	continue;
			if(dis+adj[u][v]<d[v]){
				d[v]=dis+adj[u][v];
				pq.push(mp(-d[v],v));
				path[v]=u;
			}
		}
	}
	return false;
}

void showPath(int s,int now,int *path,int *id)
{
	if(now==s){ cout<<id[s]; return; }
	showPath(s,path[now],path,id);
	cout<<' '<<id[now];
}

int main()
{
	for(;cin>>n,n;){
		for(int i=0;i<n;i++)	cin>>id[i]>>x[i]>>y[i];

		for(int i=0;i<n;i++)for(int j=0;j<n;j++)	adj[i][j]=(i==j?0:inf);
		for(int i=0;i<n;i++)for(int j=0;j<n;j++){
			int xx=x[i]-x[j],yy=y[i]-y[j];
			if(xx*xx+yy*yy<=50*50)	adj[i][j]=sqrt(xx*xx+yy*yy);
		}

		int m;	cin>>m;
		while(m--){
			int sid,gid;	cin>>sid>>gid;
			int s,g;
			for(int i=0;i<n;i++){
				if(id[i]==sid)	s=i;
				if(id[i]==gid)	g=i;
			}

			int path[1000];
			if(Dijkstra(s,g,path)){
				showPath(s,g,path,id);
				cout<<endl;
			}
			else	cout<<"NA"<<endl;
		}
	}

	return 0;
}