// #155
// 経路は未実装

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

#define sqr(x) (x)*(x)

using namespace std;

const int Size = 1100;
const int Limit = 999999;

typedef struct {
  int x;
  int y;
} Points;

int N; // # of Building
int M; // # of Move
Points Building[Size+1]; // 配列の大きさは限界より大きくする
int Ans[Size+1][Size+1];
double d[Size+1][Size+1];

void solve(void) {
  for(int k=1; k<N+1; k++) {
    for(int i=1; i<N+1; i++) {
      for(int j=1; j<N+1; j++) {
	if(d[i][j] > d[i][k]+d[k][j]) {
	  d[i][j] = d[i][k]+d[k][j];
	  Ans[i][j]=Ans[i][k];
	}
      }
    }
  }
}

int main(void) {

  while(1) {
    cin>>N;
    if(N==0) {
      break;
    }
    for(int i=0; i<N; i++) {
      Building[i].x=Building[i].y=Limit;
    }
    for(int i=0; i<N; i++) {
      int tmp;
      cin>>tmp;
      cin>>Building[tmp].x;
      cin>>Building[tmp].y;
      Ans[tmp][tmp]=tmp;
    }

    for(int i=1; i<Size+1; i++) {
      for(int j=1; j<Size+1; j++) {
	d[i][j]=hypot((Building[i].x-Building[j].x), (Building[i].y-Building[j].y));
	if(d[i][j]>50.0 || Building[i].x==Limit || Building[j].x==Limit) {
	  d[i][j]=Limit;
	}
        Ans[i][j]=j;
      }
    }

    //cout<<d[1][3]<<" "<<d[3][9]<<" "<<d[9][20]<<" "<<d[20][11]<<" "<<d[11][6]<<" "<<d[6][22]<<endl;

    solve();

    //cout<<d[1][3]<<" "<<d[1][9]<<" "<<d[1][20]<<" "<<d[1][11]<<" "<<d[1][6]<<" "<<d[1][22]<<endl;

    cin>>M;
    for(int i=0; i<M; i++) {
      int from, to;
      cin>>from;
      cin>>to;
      if(d[from][to] == Limit) {
	cout<<"NA"<<endl;
      }
      else {
	cout<<from;
	while(from!=to) {
	  cout<<" "<<Ans[from][to];
	  from=Ans[from][to];
	}
	cout<<endl;
      }
    }
  }
}