#include <iostream>
#include <cstring>
#include <vector>
#include <utility>
#include <queue>
#include <cmath>
#include <stdio.h>
using namespace std;
typedef pair< double, int > P;
const int inf = 1LL << 20;
int x[200],y[200];
int pre[200];
double d[200];
main()
{
    int n;
    while( cin >> n, n )
    {
        /// key is b;distance of b
        for( int i = 0; i < n; i++ ) 
        {
            int b,X,Y;
            cin >> b >> X >> Y;
            b--;
            x[b] = X;y[b] = Y;
        }
        vector< P > E[200];
        for( int i = 0; i< n; i++ ) 
        {
            for( int j = i + 1; j < n; j++ )
            {
                double f = sqrt( ( double )( x[i] - x[j] ) * ( x[i] - x[j] ) + ( y[i] - y[j] ) * ( y[i] - y[j] ) );
                if( f <= 50. )
                {
                    E[i].emplace_back( P(f, j) );E[j].emplace_back( P(f, i) ) ;
                }
            }
        }
        int m;
        cin >> m;
        for( int k = 0; k < m; k++ )
        {
            int s, g;
            cin >> s >> g;
            s--,g--;
            for( int l = 0; l < 200; l++ ) d[l] = inf;
            memset( pre, -1, sizeof( pre ) );
            priority_queue< P, vector< P >, greater<P> > q;
            d[s] = 0;
            q.push( P(0, s) );
            while( !q.empty() )
            {
                P p = q.top();
                q.pop();
                if( d[p.second] != p.first )continue;
                if( p.second == g )break;
                for( P u : E[p.second] )
                {
                    if( d[u.second] > p.first + u.first )
                    {
                        d[u.second] = p.first + u.first;
                        pre[u.second] = p.second;
                        q.push( P( d[u.second], u.second ) );

                    }
                }
            }
            if( d[g] == inf )puts("NA");
            else
            {
                vector< int > v;
                for( int u = g; ~u; v.emplace_back( u ), u = pre[u] );
                for( int i = v.size() - 1; i >= 0; i-- )
                {
                    printf( "%d", v[i] + 1);
                    if( i ) printf( " ");
                    else printf("\n");
                }
            }
        }
        
    }
    return 0;
}
