until (n = $<.gets.to_i).zero?
  buildings = n.times.map {$<.gets.split.map(&:to_i)}
  sg = $<.gets.to_i.times.map {$<.gets.split.map(&:to_i)}
  table = Hash.new {|h, k| h[k] = {}}
  buildings.combination(2) do |a, b|
    ida, xa, ya = a
    idb, xb, yb = b
    dist = (xa - xb) ** 2 + (ya - yb) ** 2
    next if dist > 50 ** 2
    table[ida][idb] = Math.sqrt(dist)
    table[idb][ida] = Math.sqrt(dist)
  end
  h = table.map {|k, v| [k, v.keys]}.to_h
  
  sg.each do |s, g|
    shortest = Hash.new(Float::INFINITY)
    pred = {}
    done = h.keys.map {|k| [k, false]}.to_h
    shortest[s] = 0
    
    loop do
      u = nil
      h.each_key do |node|
        next if done[node]
        u = node if !u or shortest[node] < shortest[u]
      end
      break unless u
      done[u] = true
      
      h[u].each do |v|
        if (a = shortest[u] + table[u][v]) < shortest[v]
          shortest[v] = a
          pred[v] = u
        end
      end
    end
    
    result = if pred[g]
      order = []
      while g
        order.unshift(g)
        g = pred[g]
      end
      order.join(" ")
    else
      "NA"
    end
    puts result
  end
end
