#define _USE_MATH_DEFINES
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>
#include <iomanip>
#include <iterator>
 
using namespace std;
 
typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
 
#define FOR(i,n) for(int i = 0; i < (n); i++)
#define sz(c) ((int)c.size())

typedef unsigned long long ull;
const int INF = (int)1e8;

int b[1000],x[1000],y[1000];

inline double SQ(double x) {return x * x;}

typedef double cost_type;
struct edge {
	int to;
	cost_type cost;
	edge(){}
	edge(int to,cost_type cost) : to(to) ,cost(cost) {}
};

typedef pair<cost_type,int> P;

void dijkstra(int s,vector<P::first_type>& cost_table,vector<vector<edge> >& edges,vector<int>* _prev = NULL){
	
	//init
	cost_table.resize((int)edges.size());
	fill(cost_table.begin(),cost_table.end(),P::first_type(INF));
	if(_prev) _prev->resize((int)edges.size());
	if(_prev) fill(_prev->begin(),_prev->end(),-1);
	
	priority_queue<P,vector<P>,greater<P> > q;
	q.push(P(0,s));
	cost_table[s] = 0;

	while(!q.empty()){
		P p = q.top(); q.pop();
		int v = p.second;
		if(cost_table[v] < p.first) continue;
		for(int i = 0; i < (int)edges[v].size(); i++){
			edge& e = edges[v][i];
			if(cost_table[e.to] > cost_table[v] + e.cost){
				cost_table[e.to] = cost_table[v] + e.cost;
				if(_prev) (*_prev)[e.to] = v;
				q.push(P(cost_table[e.to],e.to));
			}
		}
	}
}

void get_path(int t,vector<int>& prev,vector<int>& path){
	for(; t != -1; t = prev[t]) path.push_back(t);
	reverse(path.begin(),path.end());
}

int main(){
	int n;
	while(cin>>n,n){
		FOR(i,n) cin>>b[i]>>x[i]>>y[i];
		vector<vector<edge> > edges(n,vector<edge>());
		FOR(i,n) FOR(j,n){
			if(i==j) continue;
			else{
				double d = SQ(x[i]-x[j]) + SQ(y[i]-y[j]);
				if(d <= 2500) edges[i].push_back(edge(j,sqrt(d)));
			}
		}
		map<int,int> mp;
		FOR(i,n) mp[b[i]] = i;

		int n; cin>>n;
		vector<double> costs;
		vector<int> prevs;
		FOR(i,n){
			int s,g; cin>>s>>g;
			s = mp[s],g = mp[g];

			dijkstra(s,costs,edges,&prevs);
			if(prevs[g] == -1){
				puts("NA");
			} else {
			vector<int> path;
				get_path(g,prevs,path);
				FOR(j,sz(path)){
					printf("%d%c",b[path[j]],j == sz(path)-1?'\n':' ');
				}
			}
		}
	}

	return 0;
}