#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <cmath>
using namespace std;

const long long int INF = 1e9;

typedef pair<long long int,int> P;

int main(){
  int n;
  while(cin>>n,n){
    vector<pair<int,int> > building(n);
    for(int i=0;i<n;++i){
      int b,x,y;
      cin>>b>>x>>y;
      building[b-1] = make_pair(x,y);
    }
    vector<vector<int> > G(n);
    for(int i=0;i<n;++i) G[i] = vector<int>(n);
    for(int i=0;i<n;++i){
      for(int j=i;j<n;++j){
        int ax = building[i].first;
        int ay = building[i].second;
        int bx = building[j].first;
        int by = building[j].second;
        double dist = sqrt((ax-bx)*(ax-bx)+(ay-by)*(ay-by));
        G[i][j] = (dist<=50.0)?dist:INF;
        G[j][i] = (dist<=50.0)?dist:INF;
      }
    }
    int m;cin>>m;
    for(int i=0;i<m;++i){//Dijkstra(arihon)
      int s,g;cin>>s>>g;
      s--;g--;
      vector<int> prev(n);
      for(int i=0;i<n;++i)prev[i] = i;
      vector<long long int> d(n,INF);
      priority_queue<P, vector<P>, greater<P> > q;
      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;
        for(int j=0;j<G[v].size();++j){
          if(p.first + G[v][j] < d[j]){
            d[j] = p.first + G[v][j];
            //cerr<<"#"<<v+1<<" "<<j+1<<" "<<d[j]<<endl;
            q.push(P(d[j],j));
            prev[j] = p.second;
          }
        }
      }
      int x = g;
      vector<int> w;
      while(x!=s&&x!=prev[x]){w.push_back(prev[x]);x=prev[x];}
      if(w.size()){
	      for(int j=w.size()-1;j>=0;--j)cout<<w[j]+1<<" ";
	      cout<<g+1<<endl;
      }else{
      	cout<<"NA"<<endl;
      }
    }
    
  }
  return 0;
}