#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

const double INF = 1e10;
int n;
int b[110], x[110], y[110];

void solve() {
  for (int i = 0; i < n; i++) {
    cin >> b[i] >> x[i] >> y[i];
    b[i]--;
  }
  double G[110][110], dis[110][110];
  fill_n((double*)G, 110 * 110, INF);  
  fill_n((double*)dis, 110 * 110, INF);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      double d = hypot(x[i] - x[j], y[i] - y[j]);
      if (d > 50) continue;
      G[b[i]][b[j]] = dis[b[i]][b[j]] = d;
    }
  }
  for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (dis[i][k] >= INF || dis[k][j] >= INF) continue;
        dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
      }
    }
  }
  int m;
  cin >> m;
  for (int i = 0; i < m; i++) {
    int s, g;
    cin >> s >> g;
    s--, g--;
    if (dis[s][g] >= INF) {
      cout << "NA" << endl;
    } else {
      while (s != g) {
        cout << s + 1 << " ";
        for (int j = 0; j < n; j++) {
          if (j != s && G[s][j] + dis[j][g] == dis[s][g]) {
            s = j;
            break;
          }
        }
      }
      cout << g + 1 << endl;
    }
  }
}

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  while (cin >> n, n) {
    solve();
  }  

  return 0;
}
