loop do
  n = gets.to_i
  break if n.zero?
  bs = n.times.map { gets.split.map(&:to_i) }
  sb = {}
  bs.each_with_index {|(b, *_), i| sb[b] = i }
  dp = Array.new(n) { Array.new n, Float::INFINITY }
  ps = Array.new(n) { Array.new n }
  n.times {|i| dp[i][i] = 0 }
  n.times.to_a.combination(2) do |i, j|
    d = Math.sqrt (bs[j][1]-bs[i][1])**2+(bs[j][2]-bs[i][2])**2
    if d <= 50
      dp[i][j] = dp[j][i] = d
      ps[i][j] = i
      ps[j][i] = j
    end
  end
  n.times do |k|
    n.times do |i|
      n.times do |j|
        d = dp[i][k] + dp[k][j]
        if d < dp[i][j]
          dp[i][j] = d
          ps[i][j] = ps[k][j]
        end
      end
    end
  end
  gets.to_i.times do
    s, g = gets.split.map {|s| sb[s.to_i] }
    if dp[s][g] < Float::INFINITY
      xs = []
      loop do
        xs << g
        break if s == g
        g = ps[s][g]
      end
      puts xs.reverse.map {|b| bs[b][0] }.join ' '
    else
      puts 'NA'
    end
  end
end