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

#define SQ(a) ((a)*(a))

struct Edge {
	int to;
	double cost;
	Edge(int to, double cost): to(to), cost(cost){}
};

struct State {
	int n;
	double sum;
	State(int n, int sum): n(n), sum(sum){}
	bool operator < (const State &t) const {
		return sum > t.sum;
	}
};

int x[1000], y[1000];
double d[1000];
int pre[1000];
vector<Edge> g[1000];

int btoi[1001];
int itob[1000];

vector<int> rec(int start, int goal)
{
	vector<int> res;
	for (int e = goal; e != -1; e = pre[e]){
		res.push_back(itob[e]);
	}
	reverse(res.begin(), res.end());
	if (res[0] != itob[start] || res[res.size() - 1] != itob[goal]){
		return vector<int>();
	}
	return res;
}

void solve(int start, int goal)
{
	fill(d, d + 1000, 1e50);
	memset(pre, -1, sizeof(pre));
	
	d[start] = 0.0;
	priority_queue<State> que;
	for (que.push(State(start, 0.0)); que.size(); que.pop()){
		State st = que.top();
		if (d[st.n] < st.sum) continue;
		for (int v = 0; v < g[st.n].size(); v++){
			Edge &e = g[st.n][v];
			if (d[e.to] < st.sum + e.cost) continue;
			d[e.to] = st.sum + e.cost;
			pre[e.to] = st.n;
			que.push(State(e.to, st.sum + e.cost));
		}
	}
	
	vector<int> route = rec(start, goal);
	if (route.size() == 0){
		puts("NA");
		return;
	}
	for (int i = 0; i < route.size(); i++){
		if (i) printf(" ");
		printf("%d", route[i]);
	}
	puts("");
}

int main()
{
	int n;
	while (scanf("%d", &n), n){
		for (int i = 0; i < n; i++) g[i].clear();
		for (int i = 0; i < n; i++){
			int b;
			scanf("%d", &b);
			btoi[b] = i;
			itob[i] = b;
			scanf("%d %d", &x[i], &y[i]);
		}
		for (int i = 0; i < n; i++){
			for (int j = 0; j < n; j++){
				if (i == j) continue;
				double dist = sqrt(SQ(x[i] - x[j]) + SQ(y[i] - y[j]));
				if (dist > 50) continue;
				g[i].push_back(Edge(j, dist));
				g[j].push_back(Edge(i, dist));
			}
		}
		
		int m;
		scanf("%d", &m);
		for (int i = 0; i < m; i++){
			int start, goal;
			scanf("%d %d", &start, &goal);
			solve(btoi[start], btoi[goal]);
		}
	}
	
	return 0;
}