#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <cassert>
#include <queue>
using namespace std;
using ll = long long;
using P = pair<double, int>;
const int INF = 1<<30;
const int MOD = 1e9 + 7;
const int MAX_N = 110;
int n, m;
struct edge
{
    int to; double cost;
    edge(int to, double cost) { this->to = to, this->cost = cost; }
};
vector<edge> G[MAX_N];
void print(vector<int> &pathway, int s, int g)
{
    vector<int> res;
    int v = g;
    while(true)
    {
        res.push_back(v);
        if(v == s) break;
        v = pathway[v];
    }
    reverse(res.begin(), res.end());
    for(int i = 0; i < res.size(); i++)
    {
        if(i) cout << " ";
        cout << res[i] + 1;
    }
    cout << endl;
}
void solve(int s, int g)
{
    vector<double> cost(n, INF);
    vector<int> pathway(n, -1);
    priority_queue<P, vector<P>, greater<P>> que;
    que.push(P(0, s));
    cost[s] = pathway[s] = 0;
    while(que.size())
    {
        P p = que.top(); que.pop();
        int v = p.second;
        if(v == g)
        {
            print(pathway, s, g);
            return;
        }
        for(int u = 0; u < G[v].size(); u++)
        {
            edge e = G[v][u];
            if(p.first + e.cost < cost[e.to])
            {
                cost[e.to] = p.first + e.cost;
                pathway[e.to] = v;
                que.push(P(cost[e.to], e.to));
            }
        }
    }
    cout << "NA" << endl;
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    while(cin >> n, n)
    {
        for(int i = 0; i < MAX_N; i++) G[i].clear();
        vector<int> id(n), x(n), y(n);
        for(int i = 0; i < n; i++)
        {
            cin >> id[i] >> x[i] >> y[i];
            id[i]--;
        }
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(i == j) continue;
                int a = x[i] - x[j], b = y[i] - y[j];
                double d = sqrt(a * a + b * b);
                if(d <= 50) G[id[i]].push_back(edge(id[j], d));
            }
        }
        cin >> m;
        for(int i = 0; i < m; i++)
        {
            int s, g; cin >> s >> g;
            s--, g--;
            solve(s, g);
        }
    }
    return 0;
}


