#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>

using namespace std;
typedef long long LL;
typedef pair<double, int> P;
typedef pair<int, int> PII;
static const double EPS = 1e-8;
static const int INF = 1e8;
#define FOR(i,k,n) for (int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
struct edge { 
  int to;
  double cost; 
  edge(int t,double c){
    to = t;
    cost = c;
  }
};
int main(void){
  int d[1001];
  int prev[1001];
  map<int,int> nti;
  int itn[1001];
  int V;
  int m;
  while(cin>>V){
    vector<edge> G[1001];
    if(V==0) break;
    vector<PII> point(V);
    REP(i,V){
      int x,y;
      cin>>itn[i]>>x>>y;
      nti[itn[i]] = i;
      point[i] = PII(x,y);
    }
    REP(i,V)REP(j,V){
      if(i==j) continue;
      double distance = (point[i].first-point[j].first)*(point[i].first-point[j].first) +
        (point[i].second-point[j].second)*(point[i].second-point[j].second);
      if(distance>50*50) continue;
      distance = sqrt(distance);
      G[i].push_back(edge(j,distance));
      G[j].push_back(edge(i,distance));
    }
    cin>>m;
    while(m--){
      int s,g;
      cin>>s>>g;
      s = nti[s]; g = nti[g];
      priority_queue<P, vector<P>, greater<P> > que;
      fill(d,d+V,INF);
      fill(prev,prev+V,-1);
      d[s] = 0;
      que.push(P(0,s));
      while(!que.empty()){
        P p = que.top(); que.pop();
        int v = p.second;
        if(d[v]<p.first) continue;
        REP(i,G[v].size()){
          edge e = G[v][i];
          if(d[e.to]>d[v]+e.cost){
            d[e.to] = d[v] + e.cost;
            prev[e.to] = v;
            que.push(P(d[e.to],e.to));
          }
        }
      }
      if(d[g]==INF){
        cout<<"NA"<<endl;
      }else{
        vector<int> ans;
        for(int t = g; t!=-1; t = prev[t]) ans.push_back(itn[t]);
        reverse(ans.begin(),ans.end());
        REP(i,ans.size()){
          if(i) cout<<" ";
          cout<<ans[i];
        }
        cout<<endl;
      }
    }
  }
  return 0;
}