#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ll, P> P3;
typedef pair<P ,P> PP;
constexpr ll MOD = ll(1e9) + 7;
constexpr int IINF = INT_MAX;
constexpr ll LLINF = LLONG_MAX;
constexpr int MAX_N = int(1e5) + 5;
constexpr double EPS = 1e-9;

int main() {
    int n, m;
    double x[100], y[100], d[100][100], dmin[100], pre[100];
    bool used[100];
    while(cin >> n, n){
        for(int i=0;i<n;i++){
            int b;
            cin >> b;
            cin >> x[b-1] >> y[b-1];
        }
        cin >> m;
        for(int i=0;i<n;i++){
            fill(d[i], d[i]+n, IINF);
        }
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                double tmp = pow(pow(x[i]-x[j],2)+pow(y[i]-y[j],2),0.5);
                if(tmp < 50 + EPS){
                    d[i][j] = tmp;
                    d[j][i] = tmp;
                }
            }
        }
        for(;m>0;m--){
            int s, g, now;
            cin >> s >> g;
            s--; g--;
            fill(dmin, dmin+n, IINF);
            fill(used, used+n, false);
            dmin[g] = 0;
            pre[g] = -1;
            now = g;
            for(int i=0;i<n;i++){
                used[now] = true;
                for(int j=0;j<n;j++){
                    if(dmin[j] > dmin[now] + d[now][j]){
                        dmin[j] = dmin[now] + d[now][j];
                        pre[j] = now;
                    }
                }
                double mi = IINF;
                for(int j=0;j<n;j++){
                    if(used[j]) continue;
                    if(mi > dmin[j]){
                        mi = dmin[j];
                        now = j;
                    }
                }
            }
            if(dmin[s] < IINF - EPS){
                cout << s+1;
                now = pre[s];
                while(now != -1){
                    cout << " " << now+1;
                    now = pre[now];
                }
                cout << endl;
            }
            else{
                cout << "NA" << endl;
            }
        }
    }
    return 0;
}

