#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>

#define f first
#define s second
#define INF (1<<29)
using namespace std;

typedef pair<int,int>pii;
typedef pair<int,pii>piii;
typedef pair<double,int>pid;

vector<pid> g[101];
pid pre[101];
double d[101];

bool dijkstra(int S, int G){
  priority_queue<pid,vector<pid>,greater<pid> > que;
  que.push(pid(0.0,S));
  for(int i=0;i<101;i++)pre[i]=pid(-1,-1);
  fill(d,d+100,INF);
  d[S]=0;
  while(!que.empty()){
    pid now = que.top();
    que.pop();
    
    if(now.s==G)return true;

    for(int i=0;i<g[now.s].size();i++){
      pid nx = g[now.s][i];
      if(d[nx.s] > now.f+nx.f){
	pre[nx.s]=now;
	d[nx.s]=now.f+nx.f;
	que.push(pid(now.f+nx.f,nx.s));
      }
    }
  }
  return false;
}

int main(void){

  int n,m;
  while(cin >> n,n>0){

    vector<piii>v(n);
    for(int i=0;i<n;i++){
      g[i].clear();
      cin >> v[i].f >> v[i].s.f >> v[i].s.s;
      v[i].f--;
    }

    for(int i=0;i<n;i++){
      for(int j=i+1;j<n;j++){
	double a = v[i].s.f-v[j].s.f;
	double b = v[i].s.s-v[j].s.s;
	double d = a*a+b*b;
	if(d <= 2500){
	  g[v[i].f].push_back(pid(sqrt(d),v[j].f));
	  g[v[j].f].push_back(pid(sqrt(d),v[i].f));
	}
      }
    }

    cin >> m;
    for(int i=0;i<m;i++){
      int S,G;
      cin >> S >> G;
      if(!dijkstra(S-1,G-1))cout << "NA" << endl;
      else {
	vector<int>res;
	int now = G-1;
	while(pre[now].s>=0){
	  res.push_back(now+1);
	  now=pre[now].s;
	}
	res.push_back(S);
	reverse(res.begin(),res.end());
	for(int i=0;i<res.size();i++)
	  cout << res[i] << (i<res.size()-1?" ":"\n");
      }
    }
  }
  
  return 0;
}