def dist(p, q)
  Math.sqrt( (p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2 )
end

INF = 1<<29
def dijkstra(n, start, goal, route, bn)
  arr = [start]
  ret = { start => start }
  min_d = [INF] * 1001
  min_d[start] = 0
  until arr.empty?
    a = arr.min{ |x, y| min_d[x] <=> min_d[y] }
    arr.delete(a)
    if a == goal
      return ret[a]
    end
    idx = bn.index(a)
    n.times do |i|
      next if idx == i
      if route[idx][i]
        d = min_d[a] + route[idx][i]
        if (old = min_d[bn[i]]) > d
          min_d[bn[i]] = d
          ret[bn[i]] = [*ret[a], bn[i]]
          if old == INF
            arr << bn[i]
          end
        end
      end
    end
  end
end

while n = gets.to_i
  break if n == 0
  bn = []
  bld = []
  n.times{ a, x, y = gets.split.map(&:to_i); bn << a; bld << [x, y] }
  route = bld.map{|a| bld.map{ |b| dist(a, b) if dist(a, b) <= 50 } }
  gets.to_i.times do
    s, g = gets.split.map(&:to_i)
    ans = dijkstra(n, s, g, route, bn)
    puts ans.nil? ? 'NA' : ans.join(' ')
  end
end