#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
using namespace std;
const int N=1001;
int F(double x,double y){return fabs(x-y)<1e-9;}
int main()
{
	int n,m,i,j,b,x,y,s,g,X[N],Y[N];
	static double D[N][N],V=1e10,t;
	while(scanf("%d",&n),n)
	{
		for(i=0;i<n;++i)scanf("%d%d%d",&b,&x,&y),X[b]=x,Y[b]=y;
		for(i=1;i<=n;++i)for(j=1;j<=n;++j)D[i][j]=D[j][i]=hypot(X[i]-X[j],Y[i]-Y[j]);
		for(scanf("%d",&m);m--;)
		{
			scanf("%d%d",&s,&g);
			typedef pair<double,int>P;
			P p;
			priority_queue<P>q;
			double d[N];
			fill(d,d+N,V);
			q.push(P(0,s));
			d[s]=0;
			while(!q.empty())
			{
				p=q.top();q.pop();
				for(i=1;i<=n;++i)
					if(t=D[p.second][i],t<=50&&d[p.second]+t<d[i])
						d[i]=d[p.second]+t,q.push(P(p.first-t,i));
			}
			if(d[g]==V)puts("NA");
			else
			{
				vector<int>v(1,g);
				for(i=g;i-s;v.push_back(i=j))for(j=1;j<=n;++j)
					if(i-j&&F(d[i],D[i][j]+d[j]))break;
				for(i=v.size()-1;i>=0;--i)printf("%d%c",v[i],i?' ':'\n');
			}
		}
	}
	return 0;
}