#include <iostream>
#include <map>
#include <algorithm>
#include <cmath>
#define INF 99999999
using namespace std;

class Point {
public:
  int x;
  int y;
  int id;
  Point(int x=0, int y=0) : x(x), y(y) {}
  Point operator -(Point p) {
    return Point(x-p.x, y-p.y);
  }
};

int main() {
  while(1) {
    int n;
    cin >> n;
    if(n == 0) break;

    Point bill[n];
    map<int, int> id_i;
    for(int i = 0; i < n; i++) {
      int id, x, y;
      cin >> id >> x >> y;
      id_i[id] = i;
      bill[i].x = x;
      bill[i].y = y;
      bill[i].id = id;
    }

    double data[n][n];
    fill(&data[0][0], &data[n-1][n-1]+1, INF);
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < n; j++) {
	data[i][j] = data[j][i]
	  = sqrt(pow((double)(bill[i].x-bill[j].x), 2)
		 +pow((double)(bill[i].y-bill[j].y), 2));
      }
    }

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

      int cost[n];
      int from[n];
      bool visited[n];
      fill(&cost[0], &cost[n], INF);
      cost[id_i[s]] = 0;
      fill(&visited[0], &visited[n], false);

      while(1) {
	int min = INF;
	int p;
	for(int i = 0; i < n; i++) {
	  if(!visited[i] && cost[i] < min) {
	    min = cost[i];
	    p = i;
	  }
	}
	if(min == INF) break;

	visited[p] = true;

	for(int i = 0; i < n; i++) {
	  if(!visited[i] && data[p][i] <= 50) {
	    int newValue = cost[p] + data[p][i];
	    if(newValue < cost[i]) {
	      cost[i] = newValue;
	      from[i] = p;
	    }
	  }
	}
      }

      if(cost[id_i[g]] == INF) {
	cout << "NA" << endl;
      } else {
	int out[n];
	out[0] = id_i[g];
	int out_lim;
	for(int i = 1; i < n; i++) {
	  if(out[i-1] == id_i[s]) {
	    out_lim = i-2;
	    break;
	  }
	  out[i] = from[out[i-1]];
	}

	cout << s;
	for(int i = out_lim; i >= 0; i--) {
	  cout << " " << bill[out[i]].id;
	}
	cout << endl;
      }
    }
  }
}