#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>

using namespace std;
#define int long long int
const double INF = 1e16;
const int MOD = 1000000007;

int di[] = {-1, 0, 1, 0, -1, 1, 1, -1};
int dj[] = {0, 1, 0, -1, 1, 1, -1, -1};

signed main(){
    

    while(1){
    int n; cin >> n;
    if(!n) break;
    vector<double> x(n);
    vector<double> y(n);
    map<int, int> mp;
    map<int, int> inv;
    for(int i = 0; i < n; i++){
        int b;
        cin >> b >> x[i] >> y[i];
        b--;
        mp[i] = b;
        inv[b] = i;
    }
    vector<vector<double> > g(n, vector<double> (n, INF));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            double dist = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
            if(dist <= 50.0 + 1e-4) g[i][j] = dist;
        }
    }

    vector<vector<double> > org(n, vector<double> (n));
    for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) org[i][j] = g[i][j];
    
    /*
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cout << g[i][j] << " ";
        }
        cout << endl;
    }*/

    for(int k = 0; k < n; k++){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                g[i][j] = min(g[i][j], g[i][k] + g[j][k]);
            }
        }
    }

    int m; cin >> m;

    for(int i = 0; i < m; i++){
        int s, t; cin >> s >> t;
        s--;
        t--;
        s = inv[s];
        t = inv[t];

        int cur = s;
        vector<int> ans;
        ans.push_back(s);
        double D = g[s][t];
        vector<int> used(n, false);
        used[s] = true;
        
        if(g[s][t] == INF){
            cout << "NA" << endl;
            continue;
        }

        while(cur != t){
            
            for(int j = 0; j < n; j++){
                if(used[j]) continue;
                
                double val = org[cur][j] + g[s][cur] + g[j][t];
                if(D - 1e-4 <= val && val <= D + 1e-4){
                    ans.push_back(j);
                    cur = j;
                    used[cur] = true;
                    break;
                }
            }

        }

        for(int i = 0; i < (int)ans.size(); i++){
            if(i + 1 == ans.size()) cout << mp[ans[i]] + 1 << endl;
            else cout << mp[ans[i]] + 1 << " ";
        }
    }

    }   

    return 0;
}

