#include<iostream>
#include<queue>
#include<vector>
#include<cmath>
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1e9
using namespace std;
struct S{
	vector<int> his;
	int p; double d;
	bool operator<(const S &a)const{
		return d<a.d;
	}
};
int main(){
	int n,m,s,g;
	while(cin>>n,n){
		double d[n][n],x[n],y[n],cost[n]; int id[n],b[1001];
		rep(i,n)cin>>id[i]>>x[i]>>y[i],b[id[i]]=i;
		rep(i,n)rep(j,n)d[i][j]=hypot(x[i]-x[j],y[i]-y[j]);
		for(cin>>m;m--;){
			cin>>s>>g;
			S cs,ns; cs.p=b[s]; cs.his.push_back(s);
			priority_queue<S> F; F.push(cs); vector<int> ans;
			rep(i,n)cost[i]=INF; cost[cs.p]=0;
			while(!F.empty()){
				cs=F.top(); F.pop();
				rep(i,n)if(0<d[cs.p][i]&&d[cs.p][i]<=50)if(cost[i]>(ns.d=cost[cs.p]+d[cs.p][i])){
					cost[i]=ns.d, ns.p=i, ns.his=cs.his, ns.his.push_back(id[i]);
					F.push(ns);
					if(i==b[g])ans=ns.his;
				}
			}
			if(cost[b[g]]==INF)cout<<"NA"<<endl;
			else rep(i,ans.size())cout<<ans[i]<<(i==ans.size()-1?"\n":" ");
		}
	}
	return 0;
}