#include <bits/stdc++.h>
using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define INF (1<<29)
#define EPS (1e-8)

int main() {
	int n;
	while (cin >> n, n) {
		vector<pair<double, double> > buil(n);
		vector<int> num(n);
		
		REP(i, n) scanf("%d %lf %lf", &num[i], &buil[i].first, &buil[i].second);
		
		vector<double> graph[n];
		REP(i, n) {
			graph[i].resize(n);
			REP(j, n) {
				if (i == j) graph[i][j] = 0.0;
				else graph[i][j] = hypot(buil[i].first - buil[j].first, buil[i].second - buil[j].second);
			}
		}
		
		int m;
		cin >> m;
		while (m--) {
			int s, g;
			scanf("%d %d", &s, &g);
			
			int sn, gn;
			REP(i, n) {
				if (num[i] == s) sn = i;
				if (num[i] == g) gn = i;
			}
			
			vector<double> dis(n, INF);
			priority_queue<pair<double, int> > pq;
			pq.push(make_pair(0.0, sn));
			vector<int> prev(n, INF);
			
			while (!pq.empty()) {
				pair<double, int> now = pq.top();
				pq.pop();
				
				int from = now.second;
				
				REP(i, n) {
					if (graph[from][i] <= 50 + EPS ) {
						double d = now.first + graph[from][i];
						if (dis[i] > d) {
							dis[i] = d;
							prev[i] = from;
							pq.push(make_pair(d, i));
						}
					}
				}
			}
			
			if (dis[gn] == INF) puts("NA");
			else {
				vector<int> ans;
				int pos = gn;
				
				while (pos != sn) {
					ans.push_back(num[pos]);
					pos = prev[pos];
				}
				ans.push_back(num[sn]);
				reverse(ans.begin(), ans.end());
				REP(i, ans.size()) printf("%d%c", ans[i], i == ans.size() - 1 ? '\n' : ' ');
			}
		}
		
	}
	return 0;
}