#include<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<n;i++)
#define INF 0x3f3f3f3f
using namespace std;
typedef pair<double, int>P;

int x[200], y[200];
int pre[200];
double d[200];

int main() {
	int n;
	while (scanf("%d", &n), n) {
		rep(i, n) {
			int b, xi, yi; scanf("%d%d%d", &b, &xi, &yi); b--;
			x[b] = xi; y[b] = yi;
		}
		vector<P>E[200];
		rep(i, n)for (int j = i + 1; j < n; j++) {
			double f = sqrt((double)(abs(x[i] - x[j])*abs(x[i] - x[j]) + abs(y[i] - y[j])*abs(y[i] - y[j])));
			if (f <= 50.) {
				E[i].push_back(P(f, j));
				E[j].push_back(P(f, i));
			}
		}
		int m; scanf("%d", &m);
		rep(k, m) {
			int s, g; scanf("%d%d", &s, &g); s--; g--;
			fill(d, d + n, INF);
			memset(pre, -1, sizeof(pre));
			priority_queue<P, vector<P>, greater<P>>que;
			d[s] = 0;
			que.push(P(0, s));
			while (!que.empty()) {
				P p = que.top(); que.pop();
				if (d[p.second] != p.first)continue;
				if (p.second == g)break;
				for (P u : E[p.second]) {
					if (d[u.second] > p.first + u.first) {
						d[u.second] = p.first + u.first;
						pre[u.second] = p.second;
						que.push(P(d[u.second], u.second));
					}
				}
			}
			if (d[g] == INF)puts("NA");
			else {
				vector<int>v;
				for (int u = g; ~u; v.push_back(u), u = pre[u]);
				for (int i = v.size() - 1; i >= 0; i--) {
					printf("%d", v[i] + 1);
					if (i)printf(" ");
					else printf("\n");
				}
			}
		}
	}
}