// 2011/08/25 Tazoe



#include <iostream>

#include <climits>
#include <stack>

using namespace std;



int main()

{

	while(true){

		int n;

		cin >> n;

		if(n==0)

			break;



		int B[1000][3];

		for(int i=0; i<n; i++)

			cin >> B[i][0] >> B[i][1] >> B[i][2];

/*

		for(int i=0; i<n; i++)

			cout << B[i][0] << ' ' << B[i][1] << ' ' << B[i][2] << endl;

*/

		int D[1000][1000];

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

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

				int dis = (B[i][1]-B[j][1])*(B[i][1]-B[j][1])+(B[i][2]-B[j][2])*(B[i][2]-B[j][2]);

				if(dis<=2500)

					D[i][j] = dis;

				else

					D[i][j] = INT_MAX;

			}

		}


		int P[1000][1000];

		for(int i=0; i<n; i++)

			for(int j=0; j<n; j++)

				P[i][j] = i;

/*
		for(int i=0; i<n; i++){

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

				if(D[i][j]==INT_MAX)

					cout << '-' << ' ';

				else

					cout << P[i][j] << ' ';

			}

			cout << endl;

		}

*/
		for(int k=0; k<n; k++){
			for(int i=0; i<n; i++){
				for(int j=0; j<n; j++){
					if(D[i][k]==INT_MAX||D[k][j]==INT_MAX)
						continue;

					if(D[i][j]>D[i][k]+D[k][j]){
						D[i][j] = D[i][k]+D[k][j];
						P[i][j] = P[k][j];
					}
				}
			}
		}
/*
		for(int i=0; i<n; i++){

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

				if(D[i][j]==INT_MAX)

					cout << '-' << ' ';

				else

					cout << P[i][j] << ' ';

			}

			cout << endl;

		}

*/
		int m;
		cin >> m;

		for(int i=0; i<m; i++){
			int s, g;
			cin >> s >> g;
			int S, G;
			for(int j=0; j<n; j++){
				if(B[j][0]==s)
					S = j;
				if(B[j][0]==g)
					G = j;
			}

			if(D[S][G]==INT_MAX){
				cout << "NA" << endl;
				continue;
			}

			stack<int> st;
			while(S!=G){
				st.push(G);
				G = P[S][G];
			}

			cout << B[S][0];
			while(!st.empty()){
				cout << ' ' << B[st.top()][0];
				st.pop();
			}
			cout << endl;
		}
	}



	return 0;

}