#include<iostream>
#include<vector>
#include<cmath>

using namespace std;

int n, m, b, i, j, x, y, s, g;
vector <pair <int, int> > map(1000);
vector <int> from(1000, 1001);

double dist(int mi, int j) {
  double d =  sqrt(1.0 * (map[j].first - map[mi].first) * (map[j].first - map[mi].first) + (map[j].second - map[mi].second) * (map[j].second - map[mi].second));
  if(d <= 50) return d;
  else        return 100000000;
} 

double dik(){
  int f[1000] = {};
  int mi = s;
  vector <int> cost(1000, 100000000);
  cost[mi] = 0;
  
  for(i = 0; i < 1000; i++) {
    f[mi] = 1;
    
    for(j = 0; j < 1000; j++)
      if(!f[j] && map[j].first != 100000000 && cost[j] > cost[mi] + dist(mi, j)) {
        cost[j] = cost[mi] + dist(mi, j);
        from[j] = mi;
      }
    int min = 200000000;
    for(j = 0; j < 1000; j++)
      if(!f[j] && min > cost[j]) min = cost[mi = j];
  }
  return cost[g];

}


int main(){
  while(cin >> n, n != 0) {
    for(i = 0; i < 1000; i++) {
      map[i].first = 100000000; map[i].second = 100000000;
    }
    
    while(n--){
      cin >> b >> x >> y;  b--;  x--;  y--;
      map[b].first = x; map[b].second = y;
    }
    
    cin >> m;
    while(m--) {
      cin >> s >> g; s--; g--;
      int ans[1000] = {};
      for(i = 0; i < 1000; i++) from[i] = 1001;
      if(dik() != 100000000) {
	
	for(i = g,j = 0; i < 1000; j++){
	  ans[j] = from[i] + 1;
	  i = from[i];
	}
	//	cout << ans[0] << ' ' << ans[1]  <<' '<< ans[2]  << ' ' << ans[3] << endl;
	for(i = j - 2; i >= 0; i--)  cout << ans[i] << ' ';
	cout << g + 1 << endl;
      }
      
      else cout << "NA" << endl;
    }
  }
  return 0;
}
    