#include<iostream>
#include<vector>
#include<set>
#include<stack>
#include<cmath>
#include<climits>
#include<cfloat>
using namespace std;

#define INF DBL_MAX
#define NONE INT_MAX
#define MAX 50.0

struct Point{double x,y;};
double dist(Point a,Point b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}

int main()
{
  int n,b,m,s,g;
  double x,y,M[1000][1000];
  while(cin>>n,n){
    vector<Point>building(n);
    for(int i=0;i<n;i++){
      cin>>b>>x>>y;
      b--;
      Point p={x,y};
      building[b]=p;
    }
    for(int i=0;i<n;i++)for(int j=0;j<n;j++){
      double t=dist(building[i],building[j]);
      if(i==j)M[i][j]=INF;
      else if(t>50.0)M[i][j]=INF;
      else M[i][j]=t;
    }

    cin>>m;
    for(int i=0;i<m;i++){
      cin>>s>>g;
      s--;g--;

      set<int>used;
      set<int>::iterator it;
      vector<double>d(n,INF);
      vector<int>p(n,NONE);
      d[s]=0;
      used.insert(s);
      while(used.size()!=n){
	bool end=true;
	double min=INF;
	int next,prev;
	for(int i=0;i<n;i++){
	  if(used.count(i))continue;
	  for(it=used.begin();it!=used.end();it++){
	    if(d[*it]+M[*it][i]<min){
	      min=d[*it]+M[*it][i];
	      next=i;
	      prev=*it;
	    }
	  }
	  if(min!=INF)end=false;
	}
	if(end)break;
	used.insert(next);
	p[next]=prev;
	d[next]=min;
      }

      stack<int>path;
      int t=g;
      while(p[t]!=NONE){
	path.push(p[t]);
	t=p[t];
      }
      if(path.size()&&path.top()==s){
	while(path.size()){
	  cout<<path.top()+1<<" ";
	  path.pop();
	}
	cout<<g+1<<endl;
      }else{
	puts("NA");
      }
    }
  }
}