#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<algorithm>
#include<unordered_map>
#include<queue>
#include<functional>
#define P pair<double,int>//cost to
using namespace std;

int x[100], y[100], k[100];
unordered_map<int, int>U;
vector<P>rinsetu[100];
double mincost[100];
int Prev[100];
vector<int>V;
int s, g;
void saiki(int a) {
	V.push_back(a);
	if (Prev[a] != s) {
		saiki(Prev[a]);
	}
}
int main() {
	int a;
	while (cin >> a, a) {
		U.clear();
		for (int b = 0; b < a; b++) {
			int c;
			scanf("%d%d%d",&c, &x[b], &y[b]);
			U[c] = b;
			k[b] = c;
			rinsetu[b].clear();
		}
		for (int b = 0; b < a; b++) {
			for (int c = b + 1; c < a; c++) {
				double d = pow(x[b] - x[c], 2)+pow(y[b] - y[c], 2);
				d = sqrt(d);
				if (d <= 50) {
					rinsetu[b].push_back(P(d, c));
					rinsetu[c].push_back(P(d, b));
				}
			}
		}
		int b; cin >> b;
		for (int c = 0; c < b; c++) {
		    scanf("%d%d", &s, &g);
			s = U[s]; g = U[g];
			fill(mincost, mincost + a, 1 << 29);
			mincost[s] = 0;
			priority_queue<P, vector<P>, greater<P>>Q;
			Q.push(P(0,s));
			while (Q.size()) {
				P t = Q.top(); Q.pop();
				if (mincost[t.second] > t.first)continue;
				for (P i : rinsetu[t.second]) {
					if (mincost[i.second] > t.first + i.first) {
						mincost[i.second] = t.first + i.first;
						Q.push(P(mincost[i.second],i.second));
						Prev[i.second] = t.second;
					}
				}
			}
			if (mincost[g] == 1 << 29) { puts("NA"); }
			else {
				V.clear();
				saiki(g);
				V.push_back(s);
				reverse(V.begin(), V.end());
				for (int i = 0; i < V.size(); i++) {
					if (i)cout << " ";
					cout << k[V[i]];
				}
				cout << endl;
			}
		}
	}
}