#include<iostream>
#include<vector>
#include<complex>
#define rep(i,n) for(int i = 0;i < n ; ++i)

using namespace std;

using ll = long long;
using Point = complex<double>;


void solve(int n){
    Point p[n];
    rep(i,n){
        int a,b,c;
        cin>>a>>b>>c;
        --a;
        p[a] = Point(b,c);
    }
    double dist[n][n];
    double d[n][n];
    rep(i,n)dist[i][i]=0;
    rep(i,n)rep(j,n){
        if(i==j)continue;
        if(abs(p[i]-p[j])<=50)dist[i][j]=abs(p[i]-p[j]);
        else dist[i][j]=1e9;
    }
    rep(i,n)rep(j,n){
        d[i][j]=dist[i][j];
    }
    rep(i,n)rep(j,n)rep(k,n){
        dist[j][k]=min(dist[j][k],dist[j][i]+dist[i][k]);
    }
    int m;
    cin>>m;
    while(m--){
        int s,t;
        cin>>s>>t;
        --s;--t;
        if(dist[s][t]>=1e8){
            cout<<"NA"<<endl;
            continue;
        }
        while(s!=t){
            cout<<s+1<<" ";
            rep(i,n){
                if(s!=i&&abs(d[s][i]+dist[i][t]-dist[s][t])<1e-5){
                    s=i;
                    break;
                }
            }
        }
        cout<<t+1<<endl;
    }
}

int main(){
    int n;
    while(cin>>n,n!=0)solve(n);
}
