using System;

namespace AOJ.Volume1
{
    public class SpiderJin
    {
        private class Building
        {
            public int No { get; private set; }
            public int X { get; private set; }
            public int Y { get; private set; }

            public bool Fix { get; set; }       // 確定フラグ
            public double Cost { get; set; }    // 総移動距離
            public int From { get; set; }       // 経路

            // コンストラクタ
            public Building(int no, int x, int y)
            {
                this.No = no;
                this.X = x;
                this.Y = y;
            }
        }

        private static double GetDistance(Building a, Building b)
        {
            int x = (a.X - b.X) * (a.X - b.X);
            int y = (a.Y - b.Y) * (a.Y - b.Y);

            return Math.Sqrt(x + y);
        }

        public static int Main()
        {
            while (true)
            {
                int n = int.Parse(Console.ReadLine());
                if (n == 0) { break; }

                var buildings = new Building[n];    // ビル情報の保持
                var distance = new double[n, n];    // ビル間の距離

                // ビルの座標を読み込む
                for (int i = 0; i < n; i++)
                {
                    var input = Console.ReadLine().Split(' ');
                    int no = int.Parse(input[0]);
                    int x = int.Parse(input[1]);
                    int y = int.Parse(input[2]);

                    buildings[i] = new Building(no, x, y);
                    distance[i, i] = 0;
                }
                // 距離の計算(50を越える場合は移動不可なので「-1」にする)
                for (int i = 0; i < n - 2; i++)
                {
                    for (int j = i + 1; j <= n - 1; j++)
                    {
                        double dis = GetDistance(buildings[i], buildings[j]);
                        if (dis > 50) { dis = -1; }
                        distance[i, j] = dis;
                        distance[j, i] = dis;
                    }
                }

                // 経路を求める
                int count = int.Parse(Console.ReadLine());
                for (int p = 0; p < count; p++)
                {
                    // スタート地点・ゴール地点
                    var input = Console.ReadLine().Split(' ');
                    int start = int.Parse(input[0]);
                    int goal = int.Parse(input[1]);

                    // ビル情報初期化と同時に開始、終了indexを探す
                    int cur_index = 0;
                    int goal_index = 0;
                    for (int i = 0; i < n; i++)
                    {
                        buildings[i].Fix = false;
                        buildings[i].Cost = double.MaxValue;
                        buildings[i].From = -1;

                        if (buildings[i].No == start) { cur_index = i; }
                        if (buildings[i].No == goal) { goal_index = i; }
                    }

                    // ダイクストラ法で距離を計算
                    buildings[cur_index].Fix = true;
                    buildings[cur_index].Cost = 0;
                    while (true)
                    {
                        // 距離を計算・次に確定するビルを探す
                        int next_index = -1;
                        double min_dist = double.MaxValue;
                        for (int i = 0; i < n; i++)
                        {
                            if (buildings[i].Fix) { continue; }

                            if (distance[cur_index, i] > 0)
                            {
                                double dis = buildings[cur_index].Cost + distance[cur_index, i];
                                if (buildings[i].Cost > dis)
                                {
                                    buildings[i].Cost = dis;
                                    buildings[i].From = cur_index;  // Fromには配列の添え字を登録(ビルのNoではない)
                                }
                            }

                            if (min_dist > buildings[i].Cost)
                            {
                                min_dist = buildings[i].Cost;
                                next_index = i;
                            }
                        }

                        // ゴールまでの距離が確定、または次のビルがない場合は終了
                        if (next_index < 0) { break; }
                        buildings[next_index].Fix = true;
                        if (buildings[next_index].No == goal) { break; }

                        cur_index = next_index;
                    }

                    // 経路を出力
                    if (buildings[goal_index].Fix)
                    {
                        string output = "";
                        int index = goal_index;
                        while (true)
                        {
                            output = " " + buildings[index].No + output;
                            index = buildings[index].From;
                            if (index < 0) { break; }
                        }

                        Console.WriteLine(output.Trim());
                    }
                    else
                    {
                        Console.WriteLine("NA");
                    }
                }
            }
            return 0;
        }
    }
}

Measured memory_bytes: 9080