#include <algorithm>
#include <map>
#include <vector>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define IREP(it,array) for(vector<int>::iterator it=array.begin(); it!=array.end(); ++it)
#define PREP(it,array) for(vector<P>::iterator it=array.begin(); it!=array.end(); ++it)
#define SREP(it,array) for(vector<string>::iterator it=array.begin(); it!=array.end(); ++it)

#define MP       make_pair
#define PB       push_back
#define ALL(x)   (x).begin(),(x).end()

const int INF = 1<<29;
const double EPS = 1e-9;
double zero(double d){
  return d < EPS ? 0.0 : d;
}

typedef long long LL;
typedef pair<double,int> P;

int main()
{
  cout.setf(ios::fixed, ios::floatfield);
  cout.precision(7);

  int n;
  while(cin>>n,n){
    pair<int,P> build[n];
    REP(i,n){
      int b,x,y;
      cin>>b>>x>>y;
      build[i].first = b;
      build[i].second.first = x;
      build[i].second.second = y;
    }

    double d[n+1][n+1];
    REP(i,n+1){
      fill( d[i], d[i]+n+1, INF );
    }
    d[0][0] = 0;
    REP(i,n){
      REP(j,n){
	P from = build[i].second;
	P to = build[j].second;
	double cost = sqrt(pow((double)from.first-to.first,2) +
			   pow((double)from.second-to.second,2));
	if(cost <= 50 ){
	  d[build[i].first][build[j].first] = 
	    d[build[j].first][build[i].first] = cost;
	}
      }
      d[i+1][i+1] = 0;
    }
    /*
    cout << "::" << d[20][18] << endl;
    cout << "::" << d[18][19] << endl;
    cout << "::" << d[19][6] << endl;

    cout << ":::" << d[20][11] << endl;
    cout << ":::" << d[11][6] << endl;
    */
    //    cout << n << endl;

    int m;
    cin>>m;
    REP(_t,m){
      int s,g;
      cin>>s>>g;
      
      priority_queue<P,vector<P>,greater<P> > que;
      double dis[n+1];
      fill( dis, dis+n+1, INF );
      int back[n+1];
      fill( back, back+n+1, INF );
      dis[s] = 0;
      que.push( P(0,s) );

      while( ! que.empty() ){
	P e = que.top(); que.pop();

	if( e.first > dis[e.second] )
	  continue;
	//	dis[e.second] = e.first;

	/*	if( e.second == g ){
	  cout << "end:" << e.second << endl;
	  break;
	  }*/

	REP(i,n+1){
	  if( dis[i] > dis[e.second] + d[e.second][i] ){
	    dis[i] = dis[e.second] + d[e.second][i];
	    que.push( P(dis[i],i) );
	    back[i] = e.second;
	  }
	}
      }

      if(dis[g]==INF){
	cout << "NA" << endl;
	continue;
      }

      vector<int> res;
      res.PB(g);

      int i=g;
      while(back[i]!=INF){
	res.PB(back[i]);
	i=back[i];
      }

      reverse(ALL(res));
      IREP(it,res){
	cout << *it << " ";
      }
      cout << endl;

    }
  }

  return 0;
}