#define _CRT_SECURE_NO_WARNINGS

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define all(c) (c).begin(), (c).end()
#define loop(i,a,b) for(int i=a; i<int(b); i++)
#define rep(i,b) loop(i,0,b)
#define each(e,c) for(auto& e:c)
#define iter(it,c) for(auto it=c.begin(); it!=c.end(); ++it)

double const inf = 1e20;
double const pi = acos(-1);
double eps = 1e-5;
double x[1024];
double y[1024];
int to_id[1024];
int to_no[1024];

double jump[1024][1024];
int n;

vi solve(int s, int g){
    static int from[1024];
    static double d[1024];
    static bool vis[1024];
    rep(i,n){
        d[i]=inf;
        vis[i]=false;
        from[i]=-1;
    }
    d[s]=0;
    while(1){
        bool fine=true;
        rep(i,n){
            if(vis[i]) continue;
            fine=false;break;
        }
        if(fine)break;
        double nd=inf;
        int v;
        rep(i,n){
            if(vis[i])continue;
            if(d[i]<nd){
                nd=d[i];v=i;
            }
        }
        if(nd==inf)break;
        vis[v]=true;
        rep(i,n){
            if(d[i]>d[v]+jump[v][i]){
                d[i]=d[v]+jump[v][i];
                from[i]=v;
            }
        }
    }
    if(d[g]==inf){
        return vi();
    }else{
        vi ans{g};
        int v=g;
        while(v!=-1){
            ans.push_back(from[v]);
            v=from[v];
        }
        return ans;
    }
}

int main(){
    while(cin>>n && n){
        rep(i,n){
            int t;
            cin>>t>>x[i]>>y[i];
            to_no[t]=i;
            to_id[i]=t;
        }
        rep(i,n)rep(j,n){
            double dx=x[i]-x[j];
            double dy=y[i]-y[j];
            double t=sqrt(dx*dx+dy*dy);
            if(t-eps>50)t=inf;
            jump[i][j]=t;
        }

        int m;cin>>m;
        rep(i,m){
            int s,g;cin>>s>>g;
            vi ans=solve(to_no[s],to_no[g]);
            if(ans.size()){
                for(int i=ans.size()-2;i>=0;i--){
                    cout << to_id[ans[i]] << (i==0?"\n":" ");
                }
            }else{
                cout << "NA" << endl;
            }
        }
    }
}