#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int main(){
  const ll INF=1000000000;
  ll n;
  while(1){
    cin >> n;
    if(n==0){
      return 0;
    }
    double dp[110][110];
    ll i,j,k,b[110],x[110],y[110];
    for(i=0;i<n;i++){
      cin >> b[i] >> x[i] >> y[i];
      b[i]--;
    }
    for(i=0;i<n;i++){
      for(j=0;j<n;j++){
        dp[i][j]=INF;
      }
    }
    for(i=0;i<n;i++){
      for(j=0;j<n;j++){
        if(sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]))<=50){
          dp[b[i]][b[j]]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
        }
      }
    }
    ll z[110][110];
    for(i=0;i<n;i++){
      for(j=0;j<n;j++){
        z[i][j]=j;
      }
    }
    for(k=0;k<n;k++){
      for(i=0;i<n;i++){
        for(j=0;j<n;j++){
          if(dp[i][j]>dp[i][k]+dp[k][j]){
            dp[i][j]=dp[i][k]+dp[k][j];
            z[i][j]=z[i][k];
          }
        }
      }
    }
    ll m,s,g;
    cin >> m;
    for(i=0;i<m;i++){
      cin >> s >> g;
      s--,g--;
      if(dp[s][g]==INF){
        cout << "NA" << endl;
        continue;
      }
      cout << s+1;
      for(j=s;j!=g;j=z[j][g]){
        cout << ' ' << z[j][g]+1;
      }
      cout << endl;
    }
  }
  return 0;
}
