#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

class Edge
{
public:
    int to;
    double cost;
    Edge(){};
    Edge(int to0, double cost0){to = to0; cost = cost0;}
};

void shortestPath(const vector<vector<Edge> >& edges, int start, vector<int>& prev)
{
    prev.assign(edges.size(), -1);
    vector<double> dist(edges.size(), DBL_MAX);
    dist[start] = 0.0;
    priority_queue<pair<double,int> ,vector<pair<double,int> >, greater<pair<double,int> > > q;
    q.push(make_pair(0.0, start));

    while(!q.empty()){
        pair<double, int> p = q.top();
        q.pop();
        int v = p.second;
        if(dist[v] < p.first)
            continue;
        for(unsigned i=0; i<edges[v].size(); ++i){
            Edge e = edges[v][i];
            if(dist[v] + e.cost < dist[e.to]){
                prev[e.to] = v;
                dist[e.to] = dist[v] + e.cost;
                q.push(make_pair(dist[e.to], e.to));
            }
        }
    }
}

int main()
{
    for(;;){
        int n;
        cin >> n;
        if(n == 0)
            return 0;

        vector<int> index(n), x(n), y(n);
        for(int i=0; i<n; ++i)
            cin >> index[i] >> x[i] >> y[i];

        vector<vector<Edge> > edges(n);
        for(int i=0; i<n; ++i){
            for(int j=0; j<n; ++j){
                double dist = sqrt(pow(x[i]-x[j], 2.0) + pow(y[i]-y[j], 2.0));
                if(dist <= 50){
                    edges[i].push_back(Edge(j, dist));
                }
            }
        }
        vector<vector<int> > prev(n);
        for(int i=0; i<n; ++i)
            shortestPath(edges, i, prev[i]);

        int m;
        cin >> m;
        for(int i=0; i<m; ++ i){
            int s, g;
            cin >> s >> g;
            s = find(index.begin(), index.end(), s) - index.begin();
            g = find(index.begin(), index.end(), g) - index.begin();

            if(prev[g][s] == -1)
                cout << "NA" << endl;
            else{
                int v = s;
                cout << index[v];
                while(v != g){
                    v = prev[g][v];
                    cout << ' ' << index[v];
                }
                cout << endl;
            }
        }
    }
}