#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>
#include <functional>
#include <utility>
#include <unordered_map>
#include <map>

#define INF 2147483647
#define INF_LL 9223372036854775807
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

struct pos { int x, y; };
int main() {
	while (1) {
		int n;
		cin >> n;
		if (n == 0)break;
		vector<pos> building(n);
		vector<vector<double> > cost(n, vector<double>(n, 0));
		for (int i = 0; i < n; i++) {
			int b;
			cin >> b; b--;
			cin >> building[b].x >> building[b].y;
		}
		for (int i = 0; i < n; i++)for (int j = 0; j < n; j++) {
			if (i == j)cost[i][j] = 0;
			else cost[i][j] = sqrt(pow(building[i].x - building[j].x, 2) + pow(building[i].y - building[j].y, 2));
			if (cost[i][j] > 50)cost[i][j] = INF_LL;
		}

		int m;
		cin >> m;
		for (int i = 0; i < m; i++) {
			int s, g, c;
			cin >> s >> g;
			s--; g--;
			c = g;
			vector<double> d(n, INF);
			vector<bool> used(n, false);
			vector<int> prev(n, -1);
			vector<int> path;
			d[s] = 0;
			while (1) {
				int v = -1;
				for (int u = 0; u < n; u++) {
					if (!used[u] && (v == -1 || d[u] < d[v])) v = u;
				}
				if (v == -1)break;
				used[v] = true;
				for (int u = 0; u < n; u++) {
					if (d[u] > d[v] + cost[v][u]) {
						d[u] = d[v] + cost[v][u];
						prev[u] = v;
					}
				}
			}
			for (; g != -1; g = prev[g]) path.push_back(g);
			reverse(path.begin(), path.end());
			if (path[0] == c && s != c)cout << "NA" << endl;
			else {
				for (int i = 0; i < path.size(); i++) {
					cout << path[i] + 1;
					if (i != path.size() - 1) cout << " ";
				}
				cout << endl;
			}
		}
	}


	return 0;
}
