#include <iostream>
#include <complex>
#include <vector>
#include <algorithm>
using namespace std;

#define INF 10e6
#define X real()
#define Y imag()
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
typedef complex<double> P;


int n; //ビルの数
P build[1001]; //ビルの座標
double graph[1001][1001];//距離グラフ
double d[1001];  //最短距離
int prev[1001];  //経路
bool used[1001]; //	訪問済み

void initial(){
	for(int i=0;i<1001;i++)
		for(int j=0;j<1001;j++)
			graph[i][j]=(abs(build[i]-build[j]))<=50.0?abs(build[i]-build[j]):INF;
	return ;
}

void dijkstra(int s){
	fill(d,d+1001,INF);
	fill(used,used+1001,false);
	fill(prev,prev+1001,-1);
	d[s]=0;
	
	while(true){
		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]+graph[u][v])
				d[u]=d[v]+graph[u][v],prev[u]=v;
		}
	}
	return ;
}

vector<int> get_path(int t){
	vector<int> path;
	for(;t!=-1;t=prev[t])path.push_back(t);
	reverse(path.begin(),path.end());
	return path;

}

int main(){
	int tem,m;
	while(cin >> n,n){
		for(int i=0;i<n;i++)
			cin >>tem,cin >>build[tem-1].X>> build[tem-1].Y;
		initial();
		cin >> m;
		for(int i=0;i<m;i++){
			int s,g,c;
			vector<int> root;
			cin >> s >> g;
			dijkstra(s-1);
			if(d[g-1]>=INF)
				cout << "NA" << endl;
			else{
				root=get_path(g-1);
				c=0;
				EACH(j,root)
					cout<< (c? " ":"") << (*j)+1,c++;
				cout << endl;
			}
		}
	}

return 0;
}