using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace ConsoleApplication1
{
    struct Point : IComparable
    {
        internal int to;
        internal double dist;
 
        public Point(int to, double dist)
        {
            this.to = to;
            this.dist = dist;
        }
 
        public int CompareTo(object obj)
        {
            Point other = (Point)obj;
 
            if (other.dist - dist > 0) return 1;    // rev
            if (other.dist == dist) return 0;
            return -1;
        }
    }
 
    struct State
    {
        internal double dist;
        internal string path;
    }
 
    class Problem
    {
        readonly int INF = 1 << 20;
        readonly int n;
 
        Dictionary<int, List<Point>> adj;
        State[][] memo;
        bool[] flg;
 
        public Problem(int n)
        {
            this.n = n;
            adj = new Dictionary<int, List<Point>>();
            memo = new State[n + 1][];
            flg = new bool[n + 1];
        }
 
        public void MakeMap()
        {
            var points = new Dictionary<int, KeyValuePair<int, int>>();
 
            for (int i = 0; i < n; i++)
            {
                string[] input = Console.ReadLine().Split(' ');
                int id = int.Parse(input[0]);
                int x = int.Parse(input[1]);
                int y = int.Parse(input[2]);
 
                points.Add(id, new KeyValuePair<int, int>(x, y));
                adj.Add(id, new List<Point>());
            }
 
            for (int i = 1; i <= n; i++)
            {
                for (int j = i + 1; j <= n; j++)
                {
                    int dx = points[i].Key - points[j].Key;
                    int dy = points[i].Value - points[j].Value;
                    double dist = Math.Sqrt(dx * dx + dy * dy);
 
                    if (dist > 50) continue;
 
                    adj[i].Add(new Point(j, dist));
                    adj[j].Add(new Point(i, dist));
                }
            }
        }
 
        public string GetPath(int s, int t)
        {
            if (!flg[s])
            {
                Dijkstra(s);
                flg[s] = true;
            }
 
            return memo[s][t].path == "" ? "NA" : memo[s][t].path;
        }
 
        private void Dijkstra(int s)
        {
            bool[] visited = new bool[n + 1];
 
            State temp;
            temp.dist = INF;
            temp.path = "";
 
            var d = Enumerable.Repeat(temp, n + 1).ToArray();
            d[s].dist = 0;
            d[s].path = s.ToString();
 
            PriorityQueue<Point> PQ = new PriorityQueue<Point>();
            PQ.Enqueue(new Point(s, 0));
 
            while (PQ.Count > 0)
            {
                Point f = PQ.Dequeue();
                int u = f.to;
                visited[u] = true;
 
                if (d[u].dist < f.dist) continue;
 
                for (int i = 0; i < adj[u].Count; i++)
                {
                    int v = adj[u][i].to;
 
                    if (visited[v]) continue;
 
                    double sumDist = d[u].dist + adj[u][i].dist;
 
                    if (d[v].dist > sumDist)
                    {
                        d[v].dist = sumDist;
                        d[v].path = d[u].path + " " + v;
 
                        PQ.Enqueue(new Point(v, d[v].dist));
                    }
                }
            }
            memo[s] = (State[])d.Clone();
        }
    }
 
    class Program
    {
        static void Main(string[] args)
        {
            StringBuilder sb = new StringBuilder();
 
            while (true)
            {
                int n = int.Parse(Console.ReadLine());
 
                if (n == 0) break;
 
                Problem pb = new Problem(n);
                pb.MakeMap();
 
                int m = int.Parse(Console.ReadLine());
 
                while (m-- > 0)
                {
                    string[] input = Console.ReadLine().Split(' ');
                    int s = int.Parse(input[0]);
                    int t = int.Parse(input[1]);
 
                    sb.AppendLine(pb.GetPath(s, t));
                }
            }
            Console.Write(sb);
        }
    }
 
    class PriorityQueue<T> where T : IComparable
    {
        List<T> heap;
        int size;
 
        public PriorityQueue()
        {
            heap = new List<T>();
        }
 
        public int Count { get { return size; } }
 
        public void Enqueue(T x)
        {
            heap.Add(x);
            int i = size++;
 
            while (i > 0)
            {
                int p = (i - 1) / 2;
 
                if (Compare(heap[p], x) <= 0) break;
 
                heap[i] = heap[p];
                i = p;
            }
            heap[i] = x;
        }
 
        public T Dequeue()
        {
            T ret = heap[0];
            T x = heap[--size];
 
            int i = 0;
            while (i * 2 + 1 < size)
            {
                int a = i * 2 + 1;
                int b = i * 2 + 2;
 
                if (b < size && Compare(heap[b], heap[a]) < 0)
                    a = b;
                if (Compare(heap[a], x) >= 0)
                    break;
 
                heap[i] = heap[a];
                i = a;
            }
            heap[i] = x;
            heap.RemoveAt(size);
            return ret;
        }
 
        private int Compare(T x, T y)
        {
            return y.CompareTo(x);
        }
    }
}