#include <cstdio>
#include <complex>

using namespace std;

const double INF = 1000000;

int main()
{
    for (;;) {
        int n, m;
        complex<double> bb[1000];
        double di[1000][1000];
        int sg[1000][2];

        // read bill
        scanf("%d", &n);
        if (n == 0)
            break;
        for (int i = 0; i < n; ++i) {
            int b, x, y;
            scanf("%d %d %d", &b, &x, &y);
            bb[b - 1] = complex<double>(x, y);
        }

        // eval distance
        // TODO: ビルの番号が 0 から n - 1 と仮定
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                di[i][j] = di[j][i] = abs(bb[i] - bb[j]);
                if (di[i][j] > 50)
                    di[i][j] = di[j][i] = INF;
                //printf("  %d to %d is %f\n", i, j, di[i][j]);
            }
        }

        // read move
        scanf("%d", &m);
        for (int i = 0; i < m; ++i) {
            scanf("%d %d", &sg[i][0], &sg[i][1]);
            --sg[i][0];
            --sg[i][1];
        }

        for (int ci = 0; ci < m; ++ci) {
            double dt[1000];
            bool vi[1000] = {};
            int from[1000] = {};
            for (int i = 0; i < n; ++i)
                dt[i] = INF;

            // Dijkstra
            int p = sg[ci][0];
            dt[p] = 0;
            from[p] = -1;
            for (;;) {
                vi[p] = true;
                //printf("  - search %d\n", p+1);
                for (int j = 0; j < n; ++j) {
                    if (!vi[j] && di[p][j] != INF && dt[j] > dt[p] + di[p][j]) {
                        dt[j] = dt[p] + di[p][j];
                        from[j] = p;
                    }
                }

                int min = INF;
                for (int j = 0; j < n; ++j) {
                    if (!vi[j] && dt[j] < min) {
                        p = j;
                        min = dt[j];
                    }
                }
                if (min == INF)
                    break;
            }

            if (dt[sg[ci][1]] == INF) {
                printf("NA\n");
            } else {
                int i, p, list[1000];
                p = list[0] = sg[ci][1];
                for (i = 1; p != -1; ++i) {
                    p = list[i] = from[p];
                }
                for (i -= 2; i >= 0; --i)
                    printf("%d%c", list[i] + 1, i == 0 ? '\n' : ' ');
            }
        }

    }

    return 0;
}