#include<vector>
#include<list>
#include<algorithm>
#include<iostream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#define dis(a,b) (a)*(a)+(b)*(b)
using namespace std;
void f(vector<int> v,vector<int> &x,int d[][1001],int p[],int c,int e,double s){
  int i;
  vector<int> w=v;
  if(c==e){
    if(p[c]==-1||p[c]>s){
      w.push_back(c);
      x=w;
      p[c]=s;
    }
  }else if(p[c]==-1||p[c]>s){
    w.push_back(c);
    p[c]=s;
    for(i=1;i<1001;i++){
      if(d[c][i]&&d[c][i]<=2500)
	f(w,x,d,p,i,e,s+sqrt(d[c][i]));
    }
  }
  return;
}
int main(){
  int i,j;
  int m,n;
  int p[1001],x[1001],y[1001],d[1001][1001];
  int *b,*e,*g;
  vector<int> v,w;
  for(;;){
    cin>>n;
    if(n==0)
      break;
    memset(d,0,sizeof(d));
    g=new int[n];
    for(i=0;i<n;i++){
      cin>>g[i];
      cin>>x[g[i]]>>y[g[i]];
      for(j=0;j<i;j++){
	d[g[i]][g[j]]=dis(x[g[i]]-x[g[j]],y[g[i]]-y[g[j]]);
	d[g[j]][g[i]]=d[g[i]][g[j]];
      }
    }
    delete[]g;
    cin>>m;
    b=new int[m];
    e=new int[m];
    for(i=0;i<m;i++)
      cin>>b[i]>>e[i];
    for(i=0;i<m;i++){
      v.clear();
      w.clear();
      memset(p,-1,sizeof(p));
      f(v,w,d,p,b[i],e[i],0.0);
      if(w.empty())
	cout<<"NA"<<endl;
      else{
	for(j=0;w.size()-1;j++)
	  cout<<w[j]<<" ";
	cout<<w[j]<<endl;
      }
    }
    delete[]b;
    delete[]e;
  }
  return 0;
}