#include <cstdio>
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <vector>
#include <cmath>
using namespace std;

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define pb push_back
#define ALL(a) (a).begin(),(a).end()

//typedef long long ll;

//const int INF = 100000000;
const int INF = 1<<28;
const int MAX_V = 1010;
const int MAX_E = 1000000;

int x[MAX_V], y[MAX_V];
double cost[MAX_V][MAX_V];
double d[MAX_V];
bool used[MAX_V];
int pre[MAX_V];
int V, E;

bool flag_end = false;

void init_cost() {
    REP(i, V) REP(j, V) cost[i][j] = INF;
}

void input() {
    scanf("%d", &V);

    if (V == 0) {
        flag_end = true;
        return;
    }

    init_cost();

    REP(i, V) {
        scanf("%*d%d%d", &x[i], &y[i]);
    }

    REP(i, V) {
        REP(j, V) {
            cost[i][j] = hypot(1.0*x[i] - x[j], 1.0*y[i] - y[j]);
        }
    }
}

//s: start
void dijkstra(int s) {
    REP(i, V) d[i] = INF;
    REP(i, V) used[i] = false;
    REP(i, V) pre[i] = -1;
    d[s] = 0.0;

    while (true) {
        int v = -1;
        REP(u, V) if (!used[u] && (v == -1 | d[u] < d[v])) v = u;

        if (v == -1) break;
        used[v] = true;

        REP(u, V) {
            if (cost[v][u] <= 50 && d[u] > d[v] + cost[v][u]) {
                d[u] = d[v] + cost[v][u];
                pre[u] = v;
            }
        }
    }
}

//t: terminal
vector<int> get_path(int t) {
    vector<int> path;
    for (; t != -1; t = pre[t]) path.pb(t);
    reverse(ALL(path));
    return path;
}

void solve() {
    int m;
    scanf("%d", &m);

    REP(i, m) {
        int s, g;
        scanf("%d%d", &s, &g);
        s--; g--;
        dijkstra(s);
        if (d[g] != INF) {
            vector<int> path = get_path(g);
            REP(i, path.size()) printf("%d ", path[i] + 1);
        } else {
            printf("NA");
        }
        printf("\n");
    }
}

int main() {
    while (true) {
        input();
        if (flag_end) return 0;
        solve();
    }
    return 0;
}