#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
#define sqr(x) ((x) * (x))
using namespace std;
int n, q, s, t, b[1009], x[1009], y[1009];
int main() {
	while (cin >> n, n) {
		for (int i = 0; i < n; i++) cin >> b[i] >> x[i] >> y[i];
		vector<vector<int> > G(n);
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				if (sqr(x[i] - x[j]) + sqr(y[i] - y[j]) <= 2500) {
					G[i].push_back(j);
					G[j].push_back(i);
				}
			}
		}
		cin >> q;
		while (q--) {
			cin >> s >> t;
			for (int i = 0; i < n; i++) {
				if (b[i] == s) {
					s = i; break;
				}
			}
			for (int i = 0; i < n; i++) {
				if (b[i] == t) {
					t = i; break;
				}
			}
			vector<double> dist(n, 1.0e+10); dist[s] = 0.0;
			vector<int> pre(n, -1);
			queue<pair<double, int> > que; que.push(make_pair(0.0, s));
			while (!que.empty()) {
				int u = que.front().second; que.pop();
				for (int e : G[u]) {
					double d2 = hypot((double)(x[u] - x[e]), (double)(y[u] - y[e]));
					if (dist[e] > dist[u] + d2) {
						dist[e] = dist[u] + d2;
						pre[e] = u;
						que.push(make_pair(-dist[e], e));
					}
				}
			}
			if (dist[t] >= 9.0e+9) cout << "NA" << endl;
			else {
				vector<int> ret;
				while (t != s) {
					ret.push_back(b[t]);
					t = pre[t];
				}
				reverse(ret.begin(), ret.end());
				cout << b[s];
				for (int i : ret) cout << ' ' << i;
				cout << endl;
			}
		}
	}
	return 0;
}