#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

const int INF = 1e8;
const int MAX_V = 1010;
const double eps = 1e-10;

double cost[MAX_V][MAX_V];
double d[MAX_V];
int prev[MAX_V];
bool used[MAX_V];
int V;

void dijkstra(int s) {
    fill(d, d + V, INF);
    fill(used, used + V, false);
    fill(prev, prev+V, -1);
    d[s] = 0;
    while(true) {
        int v = -1;
        for(int u=0; u < V; u++){
            if (!used[u] && (v == -1 || d[u] < d[v])) v = u;
        }
        if (v == -1) break;
        used[v] = true;

        for(int u=0; u < V; u++){
            if(d[u] > d[v] + cost[v][u]){
                d[u] = d[v] + cost[v][u];
                prev[u] = v;
            }
        }
    }
}

vector<int> get_path(int t){
    vector<int> path;
    for(; t != -1; t = prev[t]) path.push_back(t);
    reverse(path.begin(), path.end());
    return path;
}

int main(){
    while(cin >> V, V){
        for(int i=0; i< 1010; i++) for(int j=0; j< 1010; j++) cost[i][j] = INF;
        int b[1010];
        int bb[1010];
        double x[1010], y[1010];
        for(int i=0; i< V; i++){
            cin >> b[i] >> x[i] >> y[i];
            bb[b[i]] = i;
        }
        for(int i=0; i < V; i++){
            for(int j=0; j < V; j++){
                if(i == j) continue;
                double d = sqrt(pow(abs(x[i]-x[j]), 2)+pow(abs(y[i]-y[j]), 2));
                if(d-eps <=  50.0){
                    cost[i][j] = d;
                }
            }
        }
        int m;
        cin >> m;
        for(int p=0; p < m; p++){
            int s, g;
            cin >> s >> g;
            dijkstra(bb[s]);
            vector<int> path = get_path(bb[g]);
            if(path.size() ==1) cout << "NA" << endl;
            else{
                for(int i=0; i< path.size(); i++) cout << (i==0?"": " ") << b[path[i]];
                cout << endl;
            }
        }
    }
}