#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#include<sstream>
#include<iomanip>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef pair<double,int> pdi;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<pii> vp;
typedef vector<pdd> vdd;
typedef vector<pair<double,int> >vdi;
typedef vector<vp> vvp;
typedef pair<int,pii> pip;
typedef vector<pip>vip	;
const double PI=acos(-1);
const double EPS=1e-8;
const int inf=1e8;
int main(){
	int n;
	while(cin>>n,n){
		vi m(n);
		map<int,int>M;
		vp in(n);
		rep(i,n){
			int a,b,c;
			cin>>a>>b>>c;
			m[i]=a;
			M[a]=i;
			in[i]=pii(b,c);
		}
		vvd cost(n,vd(n,inf));
		rep(i,n)rep(j,i){
			double dis=hypot(in[i].first-in[j].first,in[i].second-in[j].second);
			if(dis<EPS+50)cost[i][j]=cost[j][i]=dis;
		}
		int N;
		cin>>N;
		while(N--){
			int a,b;
			cin>>a>>b;
			a=M[a],b=M[b];
			
			vi visit(n);
			vdi d(n,pdi(inf,inf));
			d[a]=pdi(0,0);
			while(1){
				int v=-1;
				rep(i,n)if(visit[i]==0&&(v==-1||d[v].first>d[i].first))v=i;
				if(v==-1)break;
				visit[v]=true;
				rep(i,n)if(d[v].first+cost[v][i]<d[i].first){
					d[i]=pdi(d[v].first+cost[i][v],v);
				}
			}
			if(abs(d[b].first-inf)<EPS)cout<<"NA"<<endl;
			else{
				vi out;
				out.pb(b);
				while(b!=a){
					out.pb(d[b].second);
					b=d[b].second;
				}
				for(int i=out.size()-1;i>=0;i--)
					cout<<m[out[i]]<<(i?" ":"\n");
			}
		}
	}
}