#include<iostream>
#include<cstring>
#include<algorithm>
#include<math.h>
#include<vector>

using namespace std;

double MapData[101][101];
int XbyId[101], YbyId[101], N;
vector<int> Path;

const int INF = 1000000;


void Init() {
	for (int i = 0; i < 100; i++) {
		XbyId[i] = YbyId[i] = INF;
		for (int j = 0; j < 100; j++) {
			MapData[i][j] = INF;
		}
	}
}

void createMap() {
	double dis;

	for (int i = 0; i < 100; i++) {
		for (int j = 0; j < 100; j++) {
			if (i == j || XbyId[i] == INF || XbyId[j] == INF) {
				continue;
			}
			dis = sqrt( pow(XbyId[i]-XbyId[j], 2) + pow(YbyId[i]-YbyId[j], 2) );
			if (dis > 50) {
				continue;
			}
			MapData[i][j] = dis;
		}
	}
}

void solve(int start, int end) {
	double dist[100];
	bool used[100];
	int preNode[100], current;

	fill(dist, dist + N, INF);
	fill(used, used + N, false);
	fill(preNode, preNode + N, -1);
	dist[start] = 0;

	while (true) {
		current = -1;

		for (int i = 0; i < N; i++) {
			if (!used[i] && (current == -1 || dist[i] < dist[current])) {
				current = i;
			}
		}
		if (current == -1) {
			break;
		}
		used[current] = true;

		for (int next = 0; next < N; next++) {
			if (dist[next] > dist[current] + MapData[current][next]) {
				dist[next] = dist[current] + MapData[current][next];
				preNode[next] = current;
			}
		}
	}

	if (dist[end] == INF) {
		cout << "NA";
		return;
	}

	current = end;
	while (current != -1) {
		Path.push_back(current);
		current = preNode[current];
	}
	reverse(Path.begin(), Path.end());
}

int main() {
	int m,start,end;

	while (cin >> N, N) {
		Init();
		for (int i = 0; i < N; i++) {
			cin >> m;
			--m;
			cin >> XbyId[m] >> YbyId[m];
		}
		createMap();

		cin >> m;
		for (int i = 0; i < m; i++) {
			cin >> start >> end;
			Path.clear();
			solve(--start, --end);
			for (int i = 0; i < Path.size(); i++) {
				cout << Path[i] + 1;
				if (i != Path.size()-1) {
					cout << " ";
				}
			}
			cout << endl;
		}
	}

	return 0;
}

