#include <iostream>
#include <cmath>
#define INF (1<<21)
using namespace std;

int main(){
  int i,j,n,m,a[1001],x[1001],y[1001],s,g,cost,f[1001],pi[1001],pj[1001],p,sum;
  double G[1001][1001],d[1001],min;
  while(1){
    cin >> n;
    if(n == 0) break;
    for(i=0;i<n;i++){
      for(j=0;j<n;j++){
	G[i][j] = INF;
      }
    }

    for(i=0;i<n;i++){
      cin >> a[i] >> x[i] >> y[i];
    }

    for(i=0;i<n;i++){
      for(j=i+1;j<n;j++){
	if(sqrt( pow((double)x[i] - x[j],2) + pow((double)y[i] - y[j],2)) <= 50.0) G[i][j] = G[j][i] = sqrt( pow((double)x[i] - x[j],2) + pow((double)y[i] - y[j],2));
      }
    }

    cin >> m;
    for(int k=0;k<m;k++){ 
      
      cin >> s >> g;

      for(i=0;i<n;i++){
	if(a[i] == s) s = i;
	else if(a[i] == g) g = i;
	d[i] = INF;
	f[i] = 0;
      }
      
      d[s] = 0;
      while(1){
	min = INF;
	for(i=0;i<n;i++){
	  if(d[i]<min && f[i] == 0){
	    min = d[i];
	    p = i;
	  }
	}
	if(min == INF) break;
	f[p] = 1;
	for(i=0;i<n;i++){
	  if(f[i] == 1) continue;
	  if(G[p][i] + d[p]< d[i]){
	    d[i] = G[p][i] + d[p];
	    pi[i] = p;
	  }
	}
      }

      if(d[g] == INF) cout << "NA";
      else{
	pi[s] = -1;
	cout << a[s];
	for(i = 0; g != -1; g = pi[g]){
	  pj[i] = g;
	  i++;
	}
	for(j = i - 2; j >= 0; j--) cout << " " << a[pj[j]];
      }
      cout << endl;

    }
  }
  return 0;
}