#include <bits/stdc++.h>
using namespace std;

typedef pair<double, int> P;

int n;

void dijkstra(int s, int g, vector<vector<pair<int, double>>> &G){
    vector<double> dist(n, 1e9);
    priority_queue<P, vector<P>, greater<P>> que;
    dist[s] = 0;
    que.emplace(0, s);

    vector<int> prev(n, -1);

    while(que.size()){
        double ccost;
        int cv;
        tie(ccost, cv) = que.top();
        que.pop();

        if(dist[cv] < ccost) continue;

        for(auto x : G[cv]){
            int nv;
            double ncost;
            tie(nv, ncost) = x;

            if(dist[cv] + ncost < dist[nv]){
                dist[nv] = dist[cv] + ncost;
                prev[nv] = cv;
                que.emplace(dist[nv], nv);
            }
        }
    }

    if(dist[g] == 1e9){
        cout << "NA" << endl;
    }
    else{
        vector<int> ans;
        for(int i=g; i!=-1; i=prev[i]){
            ans.emplace_back(i);
        }
        reverse(ans.begin(), ans.end());

        for(int i=0; i<ans.size(); i++){
            cout << ans[i] + 1 << " \n"[i == ans.size() - 1]; 
        }
    }
}

int main(){
    while(1){
        cin>>n;
        if(n == 0) return 0;
        vector<int> b(n), x(n), y(n);
        for(int i=0; i<n; i++){
            cin>>b[i]>>x[i]>>y[i];
            b[i]--;
        }

        vector<vector<pair<int, double>>> G(n);
        for(int i=0; i<n; i++){
            for(int j=i+1; j<n; j++){
                double cdist = sqrt(abs(x[i] - x[j]) * abs(x[i] - x[j]) + abs(y[i] - y[j]) * abs(y[i] - y[j]));
                if(50 < cdist) continue;
                G[b[i]].emplace_back(b[j], cdist);
                G[b[j]].emplace_back(b[i], cdist);
            }
        }

        int m; cin>>m;
        while(m--){
            int s, g; cin>>s>>g;
            s--, g--;
            dijkstra(s, g, G);
        }
    }
}
