#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<iostream>
#include<cmath>

using namespace std;
typedef vector<string>vs;
typedef vector<int>vi;
typedef vector<vi>vvi;
typedef vector<double>vd;
typedef pair<int,int>pii;
typedef long long ll;
typedef pair<ll,ll>pll;
typedef vector<ll>vl;
#define rrep(i,x,n) for(int i=(x);i<(n);++i)
#define rep(i,x) rrep(i,0,(x))
#define fi first
#define se second
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();++i)
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define pb push_back
#define maxs(a,b) (a)=max(a,b)
#define mins(a,b) (a)=min(a,b)

struct Edge{
    int to;
    double cost;
    Edge(int a,int b):
        to(a),cost(b){}
    Edge(){}
};

struct Visit{
    int pos;
    double total;
    Visit(int a,double b):
        pos(a),total(b){}
    Visit(){}
    bool operator<(const Visit &v)const{
        return total>v.total;
    }
};
const double INF=1e9;
const double EPS=1e-8;
int N;
vector<vector<Edge> >G;
int b[1000],x[1000],y[1000];

void solve(int s,int g){
    double D[1000];
    fill_n(D,1000,INF);
    priority_queue<Visit>Q;
    Q.push(Visit(s,0));
    while(!Q.empty()){
        Visit v=Q.top();
        Q.pop();
        if(D[v.pos]!=INF)continue;
        D[v.pos]=v.total;
        rep(i,G[v.pos].size()){
            Edge e=G[v.pos][i];
            if(D[e.to]!=INF)continue;
            Q.push(Visit(e.to,v.total+e.cost));
        }
    }
    if(D[g]==INF){
        puts("NA");
        return;
    }
    vi ans;
    ans.pb(g);
    while(s!=g){
        rep(i,G[g].size()){
            Edge &e=G[g][i];
            if(fabs(D[e.to]+e.cost-D[g])<EPS){
                ans.pb(e.to);
                g=e.to;
                break;
            }
        }
    }
    reverse(all(ans));
    rep(i,ans.size()){
        if(i)printf(" ");
        printf("%d",b[ans[i]]);
    }
    puts("");
}

int main(){
    while(scanf("%d",&N),N){
        G=vector<vector<Edge> >(N);
        rep(i,N){
            scanf("%d%d%d",&b[i],&x[i],&y[i]);
            rep(j,i){
                double dist=sqrt(pow(x[i]-x[j],2)+pow(y[i]-y[j],2));
                if(dist<=50.0){
                    G[i].pb(Edge(j,dist));
                    G[j].pb(Edge(i,dist));
                }
            }
        }

        int M;
        scanf("%d",&M);
        while(M--){
            int s,g;
            scanf("%d%d",&s,&g);
            rep(i,N){
                if(b[i]==s){
                    s=i;
                    break;
                }
            }
            rep(i,N){
                if(b[i]==g){
                    g=i;
                    break;
                }
            }


            solve(s,g);

        }
    }

    return 0;
}