#include<iostream>
#include<cmath>
#include<vector>
#define MAX 1000+1
#define INF 999999
using namespace std;

double data[MAX][MAX];
int path[MAX];
double dist[MAX];

typedef struct node{
	double x,y;
} build;

void parse(int i, vector<int> &ans){
	if(i==-1) return;
	else{
		parse(path[i], ans);
		ans.push_back(i);
	}
}


void hantei(int s, int g, int n){
	bool visited[MAX];
	
	for(int i=0; i<n; i++){
		visited[i] = false;
		dist[i] = INF;
	}
	
	dist[s] = 0.0;
	path[s] = -1;
	
	while(1){
		int next;
		int min = INF;
		
		for(int i=0; i<n; i++){
			if( visited[i] ) continue;
			if( dist[i] < min){
				min = dist[i];
				next = i;
			}
		}
		
		if(min == INF) break;
		
		visited[next] = true;
		
		for(int j=0; j<n; j++){
			if( visited[j] ) continue;
			if( dist[next] + data[next][j] < dist[j]){
				dist[j] = dist[next] + data[next][j];
				path[j] = next;
			}
		}
	}
	
	if(dist[g] == INF) cout << "NA" << endl;
	else{
		vector<int> ans;
		parse(g,ans);
		for(int i=0; i<ans.size(); i++){
			if( i ) cout << " ";
			cout << ans[i]+1;
		}
	cout << endl;
	}
}	
	
int main(){
	build b[MAX];
	int n,m,num,s,g;
	while(cin >> n){
		if(n==0) break;
		for(int i=0; i<n; i++){
			cin >> num;
			num--;
			cin >> b[num].x >> b[num].y;
		}
		
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				if(i==j){
					data[i][j] = 0;
					continue;
				}
				data[i][j] = sqrt(pow(b[i].x - b[j].x, 2) + pow(b[i].y - b[j].y, 2));
				if(data[i][j] > 50) data[i][j] = INF;
				
			}
		}
		
		cin >> m;
		for(int i=0; i<m; i++){
			cin >> s >> g;
			hantei(s-1,g-1,n);
		}
	}
	return 0;
}