#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

#define rep(i, n)for((i) = 0;(i) < (n);++(i))

struct buil{
	int n;
	string b;
	double x, y;
	void next(void){ cin >> b >> x >> y; n = stoi(b); return; }
};

bool nsort(buil qwe, buil rty){ return qwe.n < rty.n; }
buil B[100];
pair<double, string> G[100][100];
double ma = 12354567890.1;

int main(void){
	int i, j, k, n, m;
	for(;;){
		scanf("%d", &n);
		if(!n)break;
		rep(i, n)rep(j, n)G[i][j].first = ma;

		rep(i, n)B[i].next();
		sort(B, B + n, nsort);

		rep(i, n)rep(j, i){
			double tmp = (B[i].x - B[j].x) * (B[i].x - B[j].x) + (B[i].y - B[j].y) * (B[i].y - B[j].y);
			if(tmp <= 2500.0){
				G[i][j].first = sqrt(tmp); G[i][j].second = B[i].b;
				G[j][i].first = sqrt(tmp); G[j][i].second = B[j].b;
			}
		}
		rep(k, n)rep(i, n)rep(j, n)if(G[i][j].first > G[i][k].first + G[k][j].first){
			G[i][j].first = G[i][k].first + G[k][j].first;
			G[i][j].second = G[i][k].second + " " + G[k][j].second;
		}

		scanf("%d", &m);
		for(;m--;){
			scanf("%d %d", &i, &j);
			if(G[i - 1][j - 1].first < ma)cout << G[i - 1][j - 1].second << " " << B[j - 1].b << endl;
			else puts("NA");
		}
	}
	
	return 0;
}