#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

double x[100];
double y[100];

typedef double W;

const W INF = 1e9;

struct edge {
	int to;
	W cost;
};
typedef pair<W, int> P;
typedef vector<vector <edge > > Graph;


void dijkstra(int s, const Graph& G, vector<W>& d, vector<int>& prev) {
	priority_queue< P, vector<P>, greater<P> > que;
	fill(d.begin(), d.end(), INF);
	fill(prev.begin(), prev.end(), -1);

	d[s] = 0;
	que.push(P(0, s));
	while(!que.empty()) {
		P 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) {
				prev[e.to] = v;
				d[e.to] = d[v] + e.cost;
				que.push(P(d[e.to], e.to));
			}
		}
	}
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int n, m;
	while(cin >> n, n) {
		for(int i = 0; i < n; i++) {
			int b;
			double xx, yy;
			cin >> b >> xx >> yy;
			b--;
			x[b] = xx, y[b] = yy;
		}

		Graph G(n);
		for(int i = 0; i < n; i++) {
			for(int j = i + 1; j < n; j++) {
				double dx = x[i] - x[j];
				double dy = y[i] - y[j];
				double dist = sqrt(dx * dx + dy * dy);
				if(dist <= 50) {
					G[i].push_back({ j, dist });
					G[j].push_back({ i, dist });
				}
			}
		}

		cin >> m;
		vector<double> d(n);
		vector<int> prev(n);
		for(int i = 0; i < m; i++) {
			int s, g;
			cin >> s >> g;
			s--, g--;
			dijkstra(s, G, d, prev);
			if(d[g] == INF) {
				cout << "NA" << endl;
			}
			else {
				vector<int> ans;
				int v = g;
				ans.push_back(g);
				while(v != s) {
					v = prev[v];
					ans.push_back(v);
				}
				for(int j = ans.size() - 1; j >= 0; j--) {
					cout << ans[j] + 1;
					if(j != 0) cout << " ";
					else cout << endl;
				}
			}
		}

	}
}