#include <iostream>
#include <queue>
#include <vector>
#include <cmath>
#include <algorithm>
#define INF 100000000
using namespace std;
typedef pair<double,int> P;
struct edge {
  int to;
  double cost;
};
int n,m;
int b[1000],x[1000],y[1000];
double d[1000];
vector<edge> V[1000];
int prev[1000];

double dist(int from, int to) {
  return sqrt((x[to]-x[from])*(x[to]-x[from])+(y[to]-y[from])*(y[to]-y[from]));
}

void dijkstra(int s) {
  priority_queue <P, vector<P>, greater<P> > que;
  for(int i=0;i<n;i++) {
    d[i] = INF;
  }
  d[s] = 0;
  prev[s] = INF;
  que.push(P(0,s));

  while(!que.empty()) {
    P p = que.top();que.pop();
    int v = p.second;
    if(d[v] < p.first) continue;
    for(int i=0;i<V[v].size();i++) {
      edge e = V[v][i];
      if(d[e.to] > d[v] + e.cost) {
	d[e.to] = d[v] + e.cost;
	prev[e.to] = v;
	que.push(P(d[e.to],e.to));
      }
    }
  }
}

int main() {

  while(cin >> n) {
    if(n==0) break;
    for(int i=0;i<n;i++) {
      cin >> b[i] >> x[i] >> y[i];
    }

    for(int i=0;i<n;i++) {
      for(int j=0;j<n;j++) {
	if(j==i)continue;
	if(double r = dist(i,j) <= 50.0) {
	  edge temp;
	  temp.to = j;
	  temp.cost = r;
	  V[i].push_back(temp);
	  temp.to = i;
	  V[j].push_back(temp);
	}
      }
    }
    cin >> m;
    for(int i=0;i<m;i++) {
      int s,g,ps,pg;
      cin >> ps >> pg;
      for(int i=0;i<n;i++) {
	if(b[i] == ps) s = i;
	else if(b[i] == pg) g = i;
      }
      dijkstra(s);
      if(d[g] != INF) {
	int t = g;
	vector<int> path;
	for(;prev[t] != INF;t = prev[t]) {
	  path.push_back(t);
	}
	path.push_back(s);
	reverse(path.begin(),path.end());
	for(int i=0;i<path.size();i++) {
	  cout << (i==0 ? "":" ") << b[path[i]];
	}
	cout << endl;
	path.clear();
      }
      else
	cout << "NA" << endl;
    }

    for(int i=0;i<n;i++) {
      V[i].clear();
    }
  }
}