#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
#include <functional>
#include <algorithm>
#include <stack>

using namespace std;

typedef pair<int, int> P;
typedef pair<int, P> Q;
typedef pair<double, int> R;

struct edge {
	int to;
	double cost;
};

vector<edge> G[1005];
double d[1005];

#define INF 1000000000.0

void dijkstra(int s) {
	priority_queue<R, vector<R>, greater<R> > que;
	fill(d, d+1005, INF);
	d[s] = 0.0;
	que.push(R(0.0, s));

	while (!que.empty()) {
		R p = que.top();
		que.pop();
		int v = p.second;
		if (d[v] < p.first) continue;
		for (int i = 0; i < G[v].size(); i++) {
			edge e = G[v][i];
			if (d[e.to] > d[v] + e.cost) {
				d[e.to] = d[v] + e.cost;
				que.push(R(d[e.to], e.to));
			}
		}
	}
}

int main() {
	int n;
	while (cin >> n) {
		if (n == 0) {
			break;
		}
		for (int i = 0; i < 1005; i++) {
			G[i].clear();
		}
		vector<Q> data;
		for (int j = 0; j < n; j++) {
		int b, x, y;
		cin >> b >> x >> y;
		data.push_back(Q(b, P(x, y)));
		for (int i = 0; i < data.size()-1; i++) {
			P p = data[i].second;
			edge e;
			e.to = data[i].first;
			e.cost = sqrt((p.first-x)*(p.first-x)+(p.second-y)*(p.second-y));
			if (e.cost > 50.0) {
				continue;
			}
			G[b].push_back(e);
			e.to = b;
			G[data[i].first].push_back(e);
		}
		}
		int m;
		cin >> m;
		int s, g;
		for (int i = 0; i < m; i++) {
			cin >> s >> g;
			dijkstra(s);
			if (d[g] == INF) {
				cout << "NA" << endl;
			} else {
				stack<int> stk;
				stk.push(g);
				while (stk.top() != s) {
					int k = stk.top();
					for (int j = 0; j < G[k].size(); j++) {
						edge e = G[k][j];
						if (d[k] == d[e.to]+e.cost) {
							stk.push(e.to);
							break;
						}
					}
				}
				cout << stk.top();
				stk.pop();
				while (!stk.empty()) {
					cout << ' ' << stk.top();
					stk.pop();
				}
				cout << endl;
			}
		}
	}
	return 0;
}