#include <bits/stdc++.h>
using namespace std;
using ld = long double;
const ld eps = 1e-8;
const ld INF = 1e10;
using P = pair<ld, int>;

int main()
{
	int n, m, s, g;
	while (cin >> n, n) {
		vector<vector<P>> G(n);
		vector<ld> x(n), y(n);
		for (int i = 0, b; i < n; i++) {
			cin >> b; b--; cin >> x[b] >> y[b];
		}
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				ld dis = sqrtl((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
				if (dis <= 50.0 + eps) {
					G[i].push_back(P(dis, j));
					G[j].push_back(P(dis, i));
				}
			}
		}
		cin >> m;
		while (m--) {
			cin >> s >> g; s--; g--;
			vector<ld> d(n, INF);
			d[s] = 0;
			for (int i = 0; i < n - 1; i++) {
				for (int j = 0; j < n; j++) {
					for (auto v : G[j]) {
						d[v.second] = min(d[v.second], d[j] + v.first);
					}
				}
			}
			if (d[g] == INF) {
				cout << "NA" << endl;
				continue;
			}
			vector<int> res;
			int tmp = g; res.push_back(g + 1);
			while (tmp != s) {
				for (auto v : G[tmp]) {
					if (d[v.second] + v.first <= d[tmp] + eps) {
						res.push_back(v.second + 1);
						tmp = v.second;
						break;
					}
				}
			}
			reverse(res.begin(), res.end());
			for (int i = 0; i < (int)res.size(); i++) {
				cout << res[i] << " \n"[i + 1 == (int)res.size()];
			}
		}
	}
	return 0;
}