#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>
#include <fstream>

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define fi first
#define se second

#define PI acos(-1.0)
#define INF 1000000007
#define MOD 1000000007
#define EPS 1e-10
#define MAX_N 100100
#define MAX_M 100100

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> PD;
typedef pair<string, ll> PS;
typedef vector<ll> V;
typedef pair<P, char> PC;
typedef pair<int, string> PSI;

int n, m;

int b[1100];
double x[1100], y[1100];
int s, g;

double d[1100];
int pre[1100];

double distance(double x1, double y1, double x2, double y2){
	return sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2));
}

struct edge{
	int to;
	double cost;
};

vector<edge> ve[1100];

void djikstra(){
	fill(d, d + 1100, INF);
	fill(pre, pre + 1100, -1);

	priority_queue< pair<double,int> > que;
	
	d[s] = 0;
	que.push({ d[s], s });

	while (!que.empty()){
		pair<double, int> p = que.top();
		que.pop();
		int v = p.second;

		if (d[v] < p.first)continue;

		REP(i, ve[v].size()){
			edge e = ve[v][i];
			if (d[e.to] > d[v] + e.cost){
				d[e.to] = d[v] + e.cost;
				que.push({ d[e.to], e.to });
				pre[e.to] = v;
			}
		}
	}
}

int main(){
	while (cin >> n&&n){
		REP(i, 1100)ve[i].clear();
		REP(i, n){
			cin >> b[i] >> x[i] >> y[i];
		}
		REP(i, n){
			REP(j, n){
				double dis = distance(x[i], y[i], x[j], y[j]);
				if (i != j&&dis - 50 < EPS){
					ve[b[i]].push_back({ b[j], dis });
				}
			}
		}
		cin >> m;
		REP(i, m){
			cin >> s >> g;
			djikstra();
			int v = g;
			if (pre[v] == -1){
				cout << "NA" << endl;
				continue;
			}
			vector<int> vi;
			vi.push_back(g);
			while (pre[v] != -1){
				vi.push_back(pre[v]);
				v = pre[v];
			}
			reverse(ALL(vi));
			REP(i, vi.size()){
				if (i == 0)cout << vi[i];
				else cout << " " << vi[i];
			}
			cout << endl;
		}
	}
}