#include <iostream>
#include <cmath>
#include <queue>
#include <algorithm>
#include <memory.h>
#include <vector>
#include <map>
#include <cstdlib>
#include <ctime>
using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
typedef pair<double, int> state;
const int CLK = CLOCKS_PER_SEC;

int s, g;
double memo[100];
int pre[100];
int name[100];
double x[100];
double y[100];

map<int, int> nums;

double dis(int i, int j){
  return sqrt((x[i] - x[j])*(x[i] - x[j]) + (y[i] - y[j])*(y[i] - y[j]));
}

double heuristics(int v){
  return dis(v, nums[g]);
}

int main(){
  int n, m;
  int b;
  int cnt = 0;
  while(cin >> n &&n){
    nums.clear();
    rep(i, n){
      cin >> b >> x[i] >> y[i];
      name[i] = b;
      nums[b] = i;
    }
    cin >> m;
    for(int i = 0; i < m;i++){
      memset(pre, -1, sizeof(pre));
      fill(memo, memo + 100, 1e10);
      cin >> s >> g;
      memo[nums[s]] = heuristics(nums[s]);
      priority_queue<state, vector<state>, greater<state> > que;
      que.push(state(heuristics(nums[s]), nums[s]));
      
      while(!que.empty()){
	cnt++;
	state st = que.top();
	que.pop();
	int v = st.second;
	double fcost = st.first;
	double gcost = fcost - heuristics(v);
	if(name[v] == g){
	  break;
	}
	if(fcost > memo[v]) continue;
	for(int j = 0; j < n; j++){
	  if(j == v) continue;
	  double d = dis(v, j);
	  if(d > 50.0) continue;
	  if(memo[j] > gcost + d + heuristics(j)){
	    memo[j] = gcost + d + heuristics(j);
	    pre[j] = v;
	    que.push(state(memo[j], j));
	  }
	}
      }
      if(pre[nums[g]] == -1 && s != g){
	cout << "NA" << endl;
      }else{
	vector<int> res;
	int v = nums[g];
	res.push_back(v);
	//	for(int i = 0; i < n; i++) cout << pre[i] << " " ;
	//	cout << endl << nums[s] << endl;

	while(pre[v] >= 0){
	  v = pre[v];
	  res.push_back(v);
	}

	rep(j, (int)res.size()){
	  if(j != 0) cout << " " ;
	  cout << name[res[res.size() - 1 - j]];
	}
	cout << endl;
      }
    }
  }
  // cout << cnt << endl;
  return 0;
}