
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
using namespace std;
const int N=1001;
//near equal?
int F(double x,double y){return fabs(x-y)<1e-9;}
//IÉÜÜêévÌCfbNX
int G(const vector<int>&I,int v){return find(I.begin(),I.end(),v)-I.begin()+1;}
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)
	{
		vector<int>I;	//rÌÔÌW
		for(i=0;i<n;++i)scanf("%d%d%d",&b,&x,&y),I.push_back(b),X[I.size()]=x,Y[I.size()]=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;	//-ÅZ£AtoIndex ©firstÉ-Â¯ÄéÌYêÈ¢ÅËIftHÌless()ÅåävÈæ¤ÉI
			P p;
			priority_queue<P>q;
			double d[N];	//»ÌrÔÜÅÌÅZ£
			fill(d,d+N,V);
			//_CNXgÅÅZoHÌZo
			q.push(P(0,G(I,s)));
			d[G(I,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(I,g)]==V)puts("NA");
			else
			{
				//S[©çÔÉAÚ±³êÄ¢éÓðgÁÄ¢éàÌð½ÇÁÄ¢­
				//tÉÇÁµÄ¾ÁÄ¢éÌÅAoÍàtÉ
				//©ª©gÉ}ÂÈ°¿á¾ßæÆ
				vector<int>v(1,G(I,g));
				for(i=G(I,g);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",I[v[i]-1],i?' ':'\n');
			}
		}
	}
	return 0;
}