#include<bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef pair<int,double>P;
struct ed{int to;double co;};
ed edge;
int num[101],n,st,go,m,pre[101];
double x[101],y[101],d[101];
vector<ed>v[101];
int main(){
  while(cin>>n,n){
    map<int,int>m1,m2;
    r(i,101)v[i].clear();
    r(i,n)cin>>num[i]>>x[i]>>y[i],m1[num[i]]=i,m2[i]=num[i];
    r(i,n)r(j,n)if(i!=j){
      double dis=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
      edge.co=dis,edge.to=j;
      if(dis<=50)v[i].push_back(edge);
    }
    cin>>m;
    while(m--){
      memset(pre,-1,sizeof(pre));
      int stt,goo;
      cin>>stt>>goo;st=m1[stt];go=m1[goo];
      r(i,101)d[i]=1e9;
      d[st]=0;
      priority_queue<P,vector<P>,greater<P> >q;
      q.push(P(st,0));
      while(!q.empty()){
        P pp=q.top();q.pop();
        int tt=pp.first;
        double di=pp.second;
        if(d[tt]<di)continue;
        r(i,v[tt].size()){
          edge=v[tt][i];
          if(d[edge.to]>di+edge.co){
            pre[edge.to]=tt;
            d[edge.to]=di+edge.co;
            q.push(P(edge.to,di+edge.co));
          }
        }
      }
      if(d[go]==1e9)cout<<"NA"<<endl;
      else{
        vector<int>vv;
        for(;go!=-1;go=pre[go])vv.push_back(go);
        reverse(vv.begin(),vv.end());
        r(i,vv.size()){
          if(i)cout<<' ';
          cout<<m2[vv[i]];
        }
        cout<<endl;
      }
    }
  }
}