#include<bits/stdc++.h>
#define F first
#define S second
#define INF (1<<30)
using namespace std;
typedef pair<double,double> dP;
typedef pair<int,double> To;
typedef pair<double,int> Que;
typedef pair<int,int> P;
typedef pair< P , P > PP;
typedef struct{
  vector<To> to;
  dP zahyo;
  double mincost;
  int minpos;
  int num;
}Edge;
main(){
  Edge bill[1005];
  int n,m,s,g;
  while(1){
    cin>>n;
    for(int i=0;i<n;i++){
      int b;
      double x,y;
      cin>>b>>x>>y;
      bill[b].num=b;
      bill[b].zahyo.F=x;
      bill[b].zahyo.S=y;
    }
    for(int i=2;i<=n;i++){
      for(int j=1;j<i;j++){
	double ix=bill[i].zahyo.F;
	double iy=bill[i].zahyo.S;
	double jx=bill[j].zahyo.F;
	double jy=bill[j].zahyo.S;
	double kyori=sqrt(pow(fabs(ix-jx),2)+pow(fabs(iy-jy),2));
	if(kyori<=50){
	  bill[i].to.push_back(To(j,kyori));
	  bill[j].to.push_back(To(i,kyori));
	}
      }
    }
    cin>>m;
    for(int i=0;i<m;i++){
      for(int i=1;i<=n;i++){
	bill[i].mincost=INF;
	bill[i].minpos=-1;
      }
      cin>>s>>g;
      priority_queue<Que,vector<Que>,greater<Que> > que;
      que.push(Que(0,s));
      bill[s].mincost=0;
      bill[s].minpos=s;
      while(!que.empty()){
	Que now=que.top();
	//cout<<now.F<<" "<<now.S<<endl;
	int nb=now.S;
	que.pop();
	int size=bill[nb].to.size();
	if(bill[nb].mincost<now.F) continue;
	//cout<<"size="<<size<<endl;
	for(int i=0;i<size;i++){
	  To tob=bill[nb].to[i];
	  if(bill[tob.F].mincost>bill[nb].mincost+tob.S){
	    bill[tob.F].mincost=bill[nb].mincost+tob.S;
	    bill[tob.F].minpos=nb;
	    que.push(Que(bill[tob.F].mincost,tob.F));
	  }
	}
      }
      if(bill[g].minpos==-1){
	cout<<"NA"<<endl;
      }
      else{
	stack<int> st;
	int p=g;
	while(p!=s){
	  st.push(p);
	  p=bill[p].minpos;
	}
	st.push(s);
	while(st.size()>1){
	  cout<<st.top()<<" ";
	  st.pop();
	}
	cout<<st.top()<<endl;
	st.pop();
      }
    }
  }
}