#include<stdio.h>
#include<stack>
#include<math.h>
using namespace std;
int dd[1000][1000];
int num[1000];
int inv[1001];
int x[1000];
int y[1000];
int vv[1000];
double nowt[1000];
int rev[1000];
int main(){
	int a;
	while(scanf("%d",&a),a){
		for(int i=0;i<a;i++){
			scanf("%d%d%d",num+i,x+i,y+i);
			inv[num[i]]=i;
		}
		for(int i=0;i<a;i++)
			for(int j=0;j<a;j++)
				dd[i][j]=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
		int b;
		scanf("%d",&b);
		for(int i=0;i<b;i++){
			int c,d;
			scanf("%d%d",&c,&d);
			c=inv[c];d=inv[d];
			for(int j=0;j<a;j++){
				vv[j]=0;
				nowt[j]=999999999;
				rev[j]=-1;
			}
			nowt[c]=0;
			for(int j=0;j<a;j++){
				double M=99999999;
				int at=0;
				for(int k=0;k<a;k++){
					if(!vv[k]&&M>nowt[k]){
						M=nowt[k];
						at=k;
					}
				}
				if(M>90000000)break;
				//printf("%d\n",at);
				vv[at]=1;
				for(int k=0;k<a;k++){
					if(!vv[k]&&dd[at][k]<=2500&&nowt[k]>nowt[at]+sqrt(dd[at][k])){
						nowt[k]=nowt[at]+sqrt(dd[at][k]);
						rev[k]=at;
					}
				}
			}
			if(!vv[d])printf("NA\n");
			else {
				stack<int>S;
				int V=d;
				while(V!=c){
					S.push(V);
					V=rev[V];
				}
				printf("%d",num[c]);
				while(S.size()){
					printf(" %d",num[S.top()]);
					S.pop();
				}
				printf("\n");
			}
		}
	}
}