#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using Pi = pair<int, int>;
using Pl = pair<ll, ll>;
using Ti = tuple<int, int, int>;
using Tl = tuple<ll, ll, ll>;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define F first
#define S second
#define Get(t, i) get<(i)>((t))
#define all(v) (v).begin(), (v).end()
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i, f, n) for(int i = (int)(f); i < (int)(n); i++)
#define each(a, b) for(auto& a : b)
#define int long long

const int inf = 1 << 25;
const ll INF = 1LL << 55;

struct edge
{
  int to; double cost;
  edge(){}
  edge(int to, double cost):to(to), cost(cost){}
};

int n;
vector< vector<edge> > graph;

void dijkstra(int s, int g)
{
  typedef pair<double, int> Pd;
  
  priority_queue<Pd, vector<Pd>, greater<Pd> > que;  
  vector<double> mincost(n, INF);
  vector<int> prevv(n, -1);
  
  que.push(Pd(0.0, s));
  mincost[s] = 0.0;
  
  while(!que.empty()) {
    Pd p = que.top(); que.pop();
    if(p.S == g) break;
    if(mincost[p.S] < p.F) continue;
    for(edge e : graph[p.S]) {
      if(e.cost + p.F < mincost[e.to]) {
	mincost[e.to] = e.cost + p.F;
	prevv[e.to] = p.S;
	que.push(Pd(mincost[e.to], e.to));
      }
    }
  }
  if(mincost[g] == INF) {
    puts("NA");
    return;
  }
  vector<int> ans;
  for(int v = g; v != -1; v = prevv[v]) {
    ans.push_back(v+1);
  }
  reverse(all(ans));
  for(int i = 0; i < ans.size(); i++) {
    if(i) cout << " ";
    cout << ans[i];
  }
  cout << endl;
}

double dist(Pi a, Pi b)
{
  return sqrt((a.F-b.F)*(a.F-b.F) + (a.S-b.S)*(a.S-b.S));
}

signed main()
{
  while(cin >> n, n) {
    vector<Pi> pos(n);
    graph.clear(); graph.resize(n);
    for(int i = 0; i < n; i++) {
      int b; cin >> b; b--;
      cin >> pos[b].F >> pos[b].S;
    }
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < n; j++) {
	double d;
	if((d = dist(pos[i], pos[j])) <= 50.0){
	  graph[i].push_back(edge(j, d));
	}
      }
    }
    int m; cin >> m;
    while(m--) {
      int s, g; cin >> s >> g;
      s--, g--;
      dijkstra(s, g);
    }
  }
  return 0;
}