#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <cstring>
#include <deque>
#include <cstdio>
#include <cmath>
#include <complex>
#include <iostream>
#include <iterator>

using namespace std;

#define reep(i,f,t) for(int i=f ; i<int(t) ; ++i)
#define rep(i,n) reep(i, 0, n) 

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

struct Edge
{
	int src, dst;
	double weight;
	Edge(int src, int dst, double weight) : src(src), dst(dst), weight(weight) {}

	bool operator< (const Edge& e)const
	{
		return weight != e.weight ? weight > e.weight :
			src != e.src ? src < e.src : dst < e.dst;
	}
};

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

int main()
{
	int n;
	while(scanf("%d", &n), n){
		map<int, int> id;
		vector<pii> pts(n);
		vi preid(n);
		rep(i, n){
			int b, x, y;
			scanf("%d%d%d", &b, &x, &y);
			pts[i] = pii(x, y);
			preid[i] = b;
			id[b] = i;
		}
		
		Graph G(n);
		rep(i, n) rep(j, i){
			pii diff(pts[i].first - pts[j].first, pts[i].second - pts[j].second);
			int dist = diff.first*diff.first + diff.second*diff.second;
			if(dist <= 2500){
				double w = sqrt(dist);
				G[i].push_back(Edge(i, j, w));
				G[j].push_back(Edge(j, i, w));
			}
		}
		
		int m;
		scanf("%d", &m);
		rep(i, m){
			int s, g;
			scanf("%d%d", &s, &g);
			s = id[s];
			g = id[g];
			
			vi pre(n, -1);
			priority_queue<Edge> Q;
			Q.push(Edge(-2, s, 0.0));
			while(!Q.empty()){
				Edge e = Q.top();
				Q.pop();
				if(pre[e.dst] != -1)
					continue;
				pre[e.dst] = e.src;
				if(e.dst == g)
					break;
				
				rep(j, G[e.dst].size()){
					Q.push(Edge(e.dst, G[e.dst][j].dst, e.weight + G[e.dst][j].weight));
				}
			}
			
			if(pre[g] == -1)
				puts("NA");
			else{
				vi path;
				int now = g;
				while(now != s){
					now = pre[now];
					path.push_back(now);
				}
				
				for(int j=path.size()-1; j>=0; --j)
					printf("%d ", preid[path[j]]);
				printf("%d\n", preid[g]);
			}
		}
	}

	return 0;
}