

#include<iostream>

#include<vector>

#include<algorithm>

#include <math.h>

#include<cstdio>

using namespace std;



static const int MAX = 100;

#define INF 2000000000000ll

int V, E;

double dp[MAX][MAX];

long long prev_[MAX][MAX];

int stack[MAX], sp;



void Warshall_Floyd() {

	for (int k = 0; k < V; k++) {

		for (int i = 0; i < V; i++) {

			for (int j = 0; j < V; j++) {

				if (dp[i][k] == INF || dp[k][j] == INF) {

					continue;

				}
                if(dp[i][j]>dp[i][k]+dp[k][j]+0.0000001){
                    
				    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
                
				    prev_[i][j] = prev_[k][j];
                }

			}

		}

	}

}

void printPath2(int start, int goal) {

	int cur;



	sp = 0;

	for (cur = goal; cur != start; cur = prev_[start][cur]){

		stack[sp++] = cur;
        //cout<<cur<<endl;
        }
	stack[sp++] = start;



	while (sp--)

		printf("%d%c", stack[sp]+1, " \n"[!sp]);

}





int main() {

	while

		(cin >> V, V != 0) {

		for (int i = 0; i < V; i++) {

			for (int j = 0; j < V; j++) {

				if (i == j) {

					dp[i][j] = 0;

				}

				else {

					dp[i][j] = INF;

				}

			}

		}

		for (int i = 0; i < V; i++) {

			for (int j = 0; j < V; j++) {

				prev_[i][j] = i;

			}

		}

		vector<vector<int>>v(V, vector<int>(3));

		for (int i = 0; i < V; i++) {

			int a, b, c;

			cin >> a >> b >> c;

			v[i][0] = a-1;

			v[i][1] = b;

			v[i][2] = c;

			

		}

		for (int i = 0; i < V; i++) {

			for (int j = 0; j < V; j++) {

				if (hypot(v[i][1] - v[j][1], v[i][2] - v[j][2]) <= 50.0) {

					dp[v[i][0]][v[j][0]] = hypot(v[i][1] - v[j][1], v[i][2] - v[j][2]);

				}

				else {

					continue;

				}

			}

		}

		Warshall_Floyd();

		int q;//クエリの数

		cin >> q;

		for (int i = 0; i < q; i++) {

			int s, g;

			cin >> s >> g;
        cout<<"get"<<endl;
			s--;

			g--;

			

			if (dp[s][g] == INF) {

				cout << "NA" << endl;

			}

			else {

				printPath2(s, g);

			}

			

		}



	}

	return 0;

}
