#include <iostream>
#include <algorithm>
#include <cassert>
#include <cctype>
#include <complex>
#include <cstdio>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;

#define INF 1e9
#define rep(i,n) for(int i=0;i<n;i++)
struct edge{int to;double cost;};
typedef pair<int,int> P;

int V,n,m,x[1001],y[1001],S,G,B,X,Y,prv[1001];
double d[1001];
vector<edge> g[1001];

int main(){
	while(cin>>n&&n){
		fill(x,x+1001,-100);
		fill(y,y+1001,-100);
		rep(i,1001)g[i].clear();
		rep(i,n){cin>>B>>X>>Y;x[B]=X;y[B]=Y;}
		rep(i,1001)rep(j,1001)if(i!=j&&(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])<=2500){
			edge e;
			e.to=j;e.cost=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
			g[i].push_back(e);
			e.to=i;
			g[j].push_back(e);
		}
		cin>>m;
		rep(h,m){
			cin>>S>>G;
			priority_queue<P,vector<P>,greater<P> > q;
			fill(d,d+1001,INF);
			fill(prv,prv+1001,-1);
			d[S]=0;
			q.push(P(0,S));
			while(!q.empty()){
				P p=q.top();q.pop();
				int v=p.second;
				if(d[v]<p.first)continue;
				rep(i,g[v].size()){
					edge e=g[v][i];
					if(d[e.to]>d[v]+e.cost){
						d[e.to]=d[v]+e.cost;
						q.push(P(d[e.to],e.to));
						prv[e.to]=v;
					}
				}
			}
			//cout<<prv[S]<<endl;
			//rep(i,1001)if(prv[i]!=-1)cout<<i<<" "<<prv[i]<<endl;
			if(d[G]==INF)cout<<"NA"<<endl;
			else{
				//cout<<d[G]<<endl;
				vector<int> path;
				for(;G!=-1;G=prv[G])path.push_back(G);
				reverse(path.begin(),path.end());
				rep(i,path.size())cout<<path[i]<<(i<path.size()-1?" ":"\n");
			}
		}
	}
}