#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int MAX_N = 1000;
int n;
int s, g;
double edges[MAX_N + 1][MAX_N + 1];
int visited[MAX_N + 1];
vector<int> route;

bool shotestPath() {
	memset(visited, -1, sizeof(visited));
	typedef pair<double, pair<int, int> > P;
	priority_queue<P, vector<P>, greater<P> > que;
	que.push(make_pair(0., make_pair(s, 0)));
	while (!que.empty()) {
		P current = que.top();
		que.pop();
		const double cost = current.first;
		const int pos = current.second.first;
		const int pre = current.second.second;
		if (visited[pos] != -1) continue;
		visited[pos] = pre;
		if (pos == g) {
			return true;
		}
		for (int i = 1; i <= n; i++) {
			if (edges[pos][i] >= 0.) {
				que.push(make_pair(cost + edges[pos][i], make_pair(i, pos)));
			}
		}
	}
	return false;
}

void buildRoute(int p) {
	if (p == 0) return;
	route.push_back(p);
	buildRoute(visited[p]);
}

void solve() {
	if (shotestPath()) {
		route.clear();
		buildRoute(g);
		vector<int>::reverse_iterator it = route.rbegin();
		cout << (*it);
		for (++it; it != route.rend(); ++it) {
			cout << ' ' << (*it);
		}
		cout << endl;
	}
	else {
		cout << "NA" << endl;
	}
}

int main () {
	while (cin >> n, n) {
		double x[n], y[n];
		for (int i = 0; i < n; i++) {
			int b;
			cin >> b;
			cin >> x[b] >> y[b];
		}
		for (int i = 1; i <= n; i++) {
			for (int j = i + 1; j <= n; j++) {
				double w = x[i] - x[j];
				double h = y[i] - y[j];
				double d = w * w + h * h;
				if (d <= 50. * 50.) {
					edges[i][j] = edges[j][i] = sqrt(d);
				}
				else {
					edges[i][j] = edges[j][i] = -1.;
				}
			}
		}
		int m;
		cin >> m;
		for (int i = 0; i < m; i++) {
			cin >> s >> g;
			solve();
		}
	}
	return 0;
}