#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;

const int size = 1001;
const double inf = 1<<24;
int n;
int b[size];
int x[size], y[size];
double costs[size][size];
int con[size][size];
int con_cnt[size];

typedef pair <double, int> PDI;
typedef priority_queue <PDI, vector <PDI>, greater <PDI> > QUEUE;
double mc[size];
int prev[size];

void dijkstra_init() {
    for ( int i = 0; i < size; i++ ) {
        mc[i] = inf;
        prev[i] = -1;
    }
}

void dijkstra( int start, int goal ) {
    QUEUE Q;
    PDI start_node( 0.0, start );
    Q.push( start_node );
    mc[start] = 0.0;
    
    while ( !Q.empty() ) {
        PDI node = Q.top();
        Q.pop();

        double c = node.first;
        int v = node.second;

        if ( v == goal ) {
            vector <int> route;
            int t = v;
            route.push_back( v );
            while ( prev[t] != -1 ) {
                route.push_back( prev[t] );
                t = prev[t];
            }
            reverse( route.begin(), route.end() );
            for ( vector <int> ::iterator it = route.begin(); it != route.end(); it++ ) {
                cout << (*it) + 1;
                if ( it + 1 != route.end() ) {
                    cout << " ";
                } else {
                    cout << endl;
                }
            }
            return;
        }

        for ( int i = 0; i < con_cnt[v]; i++ ) {
            int next_v = con[v][i];
            double next_c = c + costs[v][next_v];
            if ( next_c >= mc[next_v] ) continue;
            mc[next_v] = next_c;
            prev[next_v] = v;
            PDI next_node( next_c, next_v );
            Q.push( next_node );
        }
    }

    cout << "NA" << endl;
}

int main() {
    while ( cin >> n && n ) {
        // init
        for ( int i = 0; i < n; i++ ) {
            con_cnt[i] = 0;
        }

        // input
        for ( int i = 0; i < n; i++ ) {
            int bindex;
            cin >> bindex;
            bindex--;
            cin >> x[bindex] >> y[bindex];
        }

        for ( int i = 0; i < n; i++ ) {
            for ( int j = 0; j < n; j++ ) {
                if ( i == j ) continue;
                costs[i][j] = hypot( x[i]-x[j], y[i]-y[j] );
                if ( costs[i][j] > 50.0 ) continue;
                con[i][con_cnt[i]++] = j;
            }
        }

        // proc
        int m;
        cin >> m;
        for ( int i = 0; i < m; i++ ) {
            int s, g;
            cin >> s >> g;
            dijkstra_init();
            dijkstra( s-1, g-1 );
        }
    }
    return 0;
}