#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
typedef pair< double , int > P;
typedef pair< int , P > Pii;
#define reps(i,b,n) for(int i = b ; i < n ; ++i )
#define rep(i,n) reps(i,0,n)
#define INF 10000000
#define fr first
#define sc second
#define EPS (1e-10)
double getdis(int x1,int y1,int x2,int y2){return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));}

int n,s,g;
double d[5001],dis;
int prev[5001];
struct edge{
  int to;
  double cost;
  edge(){}
  edge(int to,double cost):to(to),cost(cost){};
};
vector< vector< edge > > info;
vector<int> dijkstra(){
  vector<int> ans;
  fill_n(d,5001,INF),fill_n(prev,5001,-1);
  priority_queue<P,vector<P>,greater<P> > que;
  que.push(P(0.0,s));
  d[s] = 0.0;
  while(!que.empty()){
    P p = que.top();
    que.pop();
    double dis = p.fr;
    int now = p.sc;
    if(dis > d[now]) continue;
    if(now == g){
      ans.push_back(g);
      int furuwara = g, hayashiya;
      while(furuwara != s){
        furuwara = prev[furuwara];
        ans.push_back(furuwara);
      }
      break;
    }
    rep(i,info[now].size()){
      edge e = info[now][i];
      if(d[now] + e.cost < d[e.to]){
        d[e.to] = d[now] + e.cost;
        que.push(P(d[e.to],e.to));
        prev[e.to] = now;
      }
    }
  }
  return ans;
}
int main(){
  while(cin >> n , n){
    int id[n],x[n],y[n],m;
    rep(i,n) cin >> id[i] >> x[i] >> y[i];
    info.resize(n + 1);
    rep(i,n) rep(j,n){
      if((dis = getdis(x[i],y[i],x[j],y[j])) <= 50.0){
        info[id[i]].push_back(edge(id[j],dis));
      }
    }
    cin >> m;
    while(m--){
      cin >> s >> g;
      vector<int> ans = dijkstra();
      if(ans.empty()) cout << "NA";
      else rep(i,ans.size()) cout << ( i ? " " : "" ) << ans[ans.size()-1-i];
      cout << endl;
    }
    info.clear();
  }
}