#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,x,n) for(int i=(x);i<(n);i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define ub upper_bound
#define lb lower_bound
#define int long long
using namespace std;
const int MOD=1000000007;
const int INF=1000000009;



struct Edge{
  int src;int dst;double wei;
  Edge(int s=0,int d=0,double w=0):src(s),dst(d),wei(w){}
};

using Graph = vector<vector<Edge>>;

pair<vector<double>,vector<int>> Dij(Graph&g,int s){
    using state = pair<double,int>;//テ」ツつウテ」ツつケテ」ツδ暗」ツ?ョテァツキツ湘・ツ陳古」ツ??」ツ?ゥテ」ツ?禿」ツ?凝」ツつ嘉ィツヲツ凝」ツ?ヲテ」ツ??」ツつ凝」ツ?ョテ」ツ??
    priority_queue<state,vector<state>,greater<state>> pq;
    vector<int> from(g.size());
    vector<double> dis(g.size(),INF);
    dis[s]=0;
    pq.push(state(0,s));
    while(!pq.empty()){
      double d=pq.top().first;
      int v=pq.top().second;
      pq.pop();
      if(dis[v]<d)continue;
      rep(i,g[v].size()){
        Edge &e=g[v][i];
        if(dis[e.dst]>dis[v]+e.wei){
          dis[e.dst]=dis[v]+e.wei;
          pq.push(state(dis[e.dst],e.dst));
          from[e.dst]=v;
        }
      }
    }
    return mp(dis,from);
}

signed main(){
    int n;
    while(cin>>n,n){
    vector<pair<int,pair<int,int>>> B(n);
  //  vector<int> B(n),X(n),Y(n);
  //  rep(i,n)cin>>B[i]>>X[i]>>Y[i];
    rep(i,n){
      int a,b,c;
      cin>>a>>b>>c;
      B[i]=mp(a,mp(b,c));
    }
    sort(B.begin(),B.end());
    Graph g(n);
    rep(i,n)rep(j,n){
      if(i==j)continue;
      //double x=abs(X[i]-X[j]);
      //double y=abs(Y[i]-Y[j]);
      double x=abs(B[i].sec.fir-B[j].sec.fir);
      double y=abs(B[j].sec.sec-B[i].sec.sec);

      if(x*x+y*y<=2500.0){
        double dst=pow(x*x+y*y,0.5);
        g[i].emplace_back(i,j,dst);
        g[j].emplace_back(j,i,dst);
      }
    }

    int m;
    cin>>m;
    vector<int> S(m),G(m);
    rep(i,m)cin>>S[i]>>G[i];
    rep(i,m){
      auto ans=Dij(g,S[i]-1);
      //rep(i,n)cout<<ans.fir[i]<<' '<<ans.sec[i]<<endl;
      if(ans.fir[G[i]-1]==INF){
        cout<<"NA"<<endl;
        continue;
      }
      stack<int> path;
      for(int j=G[i]-1;;j=ans.sec[j]){
        path.push(j);
        if(j==S[i]-1)break;
      }
      while(!path.empty()){
        cout<<path.top()+1;
        if(path.size()!=1)cout<<' ';
        path.pop();
      }
      cout<<endl;
    }

  }

  return 0;
}