#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
//#include <utility>
#include <set>
#include <iostream>
//#include <memory>
#include <string>
#include <vector>
#include <algorithm>
//#include <functional>
#include <sstream>
//#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
//#include <cctype>
#include <cstring>
//#include <ctime>
#include <iterator>
#include <bitset>
//#include <numeric>
//#include <list>
//#include <iomanip>

#if __cplusplus >= 201103L
#include <array>
#include <tuple>
#include <initializer_list>
#include <unordered_set>
#include <unordered_map>
#include <forward_list>

#define cauto const auto&
#else

#endif

using namespace std;


namespace{
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
    v.assign(a, vector<T>(b, t));
}

template <class F, class T>
void convert(const F &f, T &t){
    stringstream ss;
    ss << f;
    ss >> t;
}


#define reep(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) reep((i),0,(n))
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define F first
#define S second
#define mkp make_pair
#define RALL(v) (v).rbegin(),(v).rend()


#define MOD 1000000007LL
#define EPS 1e-8
#define prev S.F
#define now S.S
static const int INF=1<<24;
typedef complex<double> P;
void mainmain(){
	int n;
	while(cin>>n,n){
		vector<P> biru;
		vint id(n);
		map<int,int>  id2;
		rep(i,n){
			int a,b,c;
			cin>>a>>b>>c;
			// cout<<a<<" "<<b<<" "<<c<<endl;
			id[i]=a;
			id2[a]=i;
			biru.PB(P(b,c));
		}
		vector<vector<pair<int,double>>> vv(n);
		rep(i,n){
			rep(j,n){
				if(i==j) continue;
				if(50.0-abs(biru[i]-biru[j])>-EPS){
					vv[j].PB(mkp(i,abs(biru[i]-biru[j])));
					// vv[i].PB(mkp(j,abs(biru[i]-biru[j])));
				}
			}
		}
		// rep(i,n){
			// cout<<i<<endl;
			// rep(j,vv[i].size()){
				// cout<<vv[i][j].F<<" "<<vv[i][j].S<<endl;
			// }
		// }
		// cout<<endl;
		int m;
		cin>>m;
		rep(i,m){
			vector<pair<double,int> >  ans(n,mkp(-1.0,-1));
			priority_queue<pair<double,pii> > pq;
			int s,g;
			cin>>s>>g;
			if(s==g){
				cout<<s<<endl;
				continue;
			}
			// cout<<s<<" "<<g<<endl;
			// cout<<id2[s]<<" "<<id2[g]<<endl;
			pq.push(mkp(0.0,mkp(id2[s],id2[s])));
			while(!pq.empty()){
				pair<double,pii> top=pq.top();
				pq.pop();
				if(ans[top.now].S!=-1) continue;
				ans[top.now]=mkp(-top.F,top.prev);
				rep(i,vv[top.now].size()){
					if(ans[vv[top.now][i].F].S==-1){
						pq.push(mkp(top.F-vv[top.now][i].S,mkp(top.now,vv[top.now][i].F)));
					}
				}
			}
			// cout<<"------"<<endl;
			// rep(i,n){
				// cout<<ans[i].F<<" "<<ans[i].S<<endl;
			// }
			if(ans[id2[g]].S==-1){
				cout<<"NA\n";
				continue;
			}
			vint ret;
			int t=id2[g];
			while(t!=id2[s]){
				ret.PB(id[t]);
				t=ans[t].S;
			}
			ret.PB(s);
			reverse(ALL(ret));
			rep(i,ret.size()){
				if(i) cout<<" ";
				cout<<ret[i];
			}
			cout<<endl;
		}
	}
}



}
main() try{
    mainmain();
}
catch(...){
}