using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

class Myon
{
    public Myon() { }
    public static int Main()
    {
        new Myon().run();
        return 0;
    }

    void run()
    {
        Scanner cin = new Scanner();
        while (true)
        {
            int n = cin.nextInt();
            if (n == 0) break;
            int[] x = new int[n];
            int[] y = new int[n];
            double[,] dist = new double[n, n];
            int[,] center = new int[n, n];
            for (int i = 0; i < n; i++)
            {
                int num = cin.nextInt() - 1;
                x[num] = cin.nextInt();
                y[num] = cin.nextInt();
            }
            double MAX = 99999999;
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    dist[i, j] = hypot(x[i] - x[j], y[i] - y[j]);
                    if (dist[i, j] > 50 + 1e-9)
                    {
                        dist[i, j] = MAX;
                    }
                    center[i, j] = -1;
                }
            }
            for (int k = 0; k < n; k++)
            {
                for (int i = 0; i < n; i++)
                {
                    for (int j = 0; j < n; j++)
                    {
                        if (dist[i, k] + dist[k, j] < dist[i, j])
                        {
                            dist[i, j] = dist[i, k] + dist[k, j];
                            center[i, j] = k;
                        }
                    }
                }
            }
            int m = cin.nextInt();
            for (int i = 0; i < m; i++)
			{
                int s = cin.nextInt();
                int g = cin.nextInt();
                if (dist[s - 1, g - 1] == MAX)
                {
                    Console.WriteLine("NA");
                }
                else
                {
                    List<int> ret = getret(dist, center, s - 1, g - 1);
                    foreach (var item in ret)
                    {
                        Console.Write(item + " ");
                    }
                    Console.WriteLine(g);
                }
			} 
            
        }

    }

    List<int> getret(double[,] dist, int[,] center, int s, int g)
    {
        List<int> ret = new List<int>();
        if (center[s, g] == -1)
        {
            ret.Add(s + 1);
            return ret;
        }
        else
        {
            List<int> r1 = getret(dist, center, s, center[s, g]);
            List<int> r2 = getret(dist, center, center[s, g], g);
            foreach (var item in r1)
            {
                ret.Add(item);
            }
            foreach (var item in r2)
            {
                ret.Add(item);
            }
            return ret;
        }
    }

    double hypot(double x, double y)
    {
        return Math.Sqrt(x * x + y * y);
    }

}

class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string next()
    {
        if (i < s.Length) return s[i++];
        s = Console.ReadLine().Split(cs, StringSplitOptions.RemoveEmptyEntries);
        i = 0;
        return s[i++];
    }

    public int nextInt()
    {
        return int.Parse(next());
    }

    public long nextLong()
    {
        return long.Parse(next());
    }

}

Measured memory_bytes: 5836