Go: package main

import (
	"bufio"
	"os"
	"strconv"
	"strings"
	"math"
	"fmt"
)

var scanner = bufio.NewScanner(os.Stdin)

func main() {
	dd := make([][]int, 1000)
	for i := range dd {
		dd[i] = make([]int, 1000)
	}
	num := make([]int,1000)
	inv := make([]int, 1001)
	x := make([]int, 1000)
	y := make([]int, 1000)
	vv := make([]int, 1000)
	nowt := make([]float64, 1000)
	rev := make([]int, 1000)
	for scanner.Scan() {
		n, _ := strconv.Atoi(scanner.Text())
		if n == 0 {
			break
		}
		for i := 0; i < n; i++ {
			scanner.Scan()
			buf1 := strings.Split(scanner.Text(), " ")
			num[i], _ = strconv.Atoi(buf1[0])
			x[i], _ = strconv.Atoi(buf1[1])
			y[i], _ = strconv.Atoi(buf1[2])
			inv[num[i]] = i
		}
		for i := 0; i < n; i++ {
			for j := 0; j < n; j++ {
				dd[i][j]=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])
			}
		}
		scanner.Scan()
		m, _ := strconv.Atoi(scanner.Text())
		for i := 0; i < m; i++ {
			scanner.Scan()
			buf2 := strings.Split(scanner.Text(), " ")
			c, _ := strconv.Atoi(buf2[0])
			d, _ := strconv.Atoi(buf2[1])
			c = inv[c]
			d = inv[d]
			for j := 0; j < n; j++ {
				vv[j] = 0
				nowt[j]=999999999
				rev[j]=-1
			}
			nowt[c]=0
			for j := 0; j < n; j++ {
				M := 99999999
				at := 0
				for k := 0; k < n; k++ {
					if vv[k] == 0 && float64(M) > nowt[k] {
						M=int(nowt[k])
						at = k
					}
				}
				if M > 90000000 {
					break
				}
				vv[at]=1
				for k := 0; k < n; k++ {
					if vv[k] == 0 && dd[at][k]<=2500&&nowt[k]>nowt[at]+math.Sqrt(float64(dd[at][k])) {
						nowt[k]=nowt[at]+math.Sqrt(float64(dd[at][k]))
						rev[k] = at
					}
				}
			}
			if vv[d] == 0 {
				fmt.Println("NA")
			} else {
				stack := make([]int, 0)
				V := d
				for V != c {
					stack = append(stack, V)
					V = rev[V]
				}
				fmt.Print(num[c])
				for len(stack) > 0 {
					fmt.Printf(" %d", num[stack[len(stack)-1]])
					stack = stack[:len(stack)-1]
				}
				fmt.Println()
			}
		}
	}
}

C++: #include <bits/stdc++.h> // {{{

#define ARG4(_1, _2, _3, _4, ...) _4
#define rep(...) ARG4(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define REP(i, a) FOR(i, 0, a)
#define FOR(i, a, b) for (int i = (a); i < (int)(b); ++i)
#define rrep(...) ARG4(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define RREP(i, a) RFOR(i, 0, a)
#define RFOR(i, a, b) for (int i = (b)-1; i >= (int)(a); --i)
#define ALL(c) (c).begin(), (c).end()
#define TEN(n) ((ll)(1e##n))
#define pb emplace_back
#define mp make_pair
#define fi first
#define se second
#define let const auto
#define USE_T template <typename T>
#define USE_Ti template <typename T = int>
#define USE_TU template <typename T, typename U>

USE_Ti using duo = std::pair<T, T>;
USE_Ti using vec = std::vector<T>;
using ll = long long;
// clang-format off
USE_TU inline bool chmax(T&x,U a){return x<a&&(x=a,1);}
USE_TU inline bool chmin(T&x,U a){return a<x&&(x=a,1);}
USE_Ti inline T in(){T x;std::cin>>x;return x;}
USE_Ti inline vec<T> in(int n){vec<T> v;v.reserve(n);rep(i,n)v.pb(in<T>());return v;}
USE_T inline void in(T*x,int n){rep(i,n)x[i]=in<T>();}
struct IoSetup {
  IoSetup(){
    using namespace std;
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout<<setprecision(10);
    cerr<<setprecision(10);
  }
} iosetup;
// clang-format on
// }}}
using namespace std;
const int inf = 1001001001;
const ll infll = 1001001001001001001ll;
const int dd[] = {0, 1, 0, -1, 0};

//{{{ orliv::graph::Graph
#ifndef INCLUDE_GRAPH_HPP
#define INCLUDE_GRAPH_HPP
#include <limits>
#include <vector>
namespace orliv {
namespace graph {
struct Edge {
  using weight_type = double;
  static constexpr weight_type INF = std::numeric_limits<weight_type>::max() - 100;

  int from, to;
  weight_type w;
  Edge(int from, int to, weight_type w = 1) : from(from), to(to), w(w) {}
  bool operator<(const Edge& rhs) const {
    if (w != rhs.w) return w > rhs.w;
    if (from != rhs.from) return from < rhs.from;
    return to < rhs.to;
  }
};

using Weight = Edge::weight_type;
using Edges = std::vector<Edge>;
using Weights = std::vector<Weight>;
using Path = std::vector<int>;
using Nodes = std::vector<int>;
}
using Graph = std::vector<graph::Edges>;
}
#endif
//}}}
//{{{ orliv::graph::shortest_path::dijkstra
#ifndef INCLUDE_GRAPH_HPP
#include "graph.hpp"
#endif
#include <algorithm>
#include <limits>
#include <queue>
namespace orliv {
namespace graph {
namespace shortest_path {
namespace util {
Path buildPath(int t, std::vector<int>& prev) {
  Path path;
  for (int u = t; u >= 0; u = prev[u]) {
    path.emplace_back(u);
  }
  std::reverse(path.begin(), path.end());
  return std::move(path);
}
}
Weights dijkstra(const Graph& g, int s, std::vector<int>& prev) {
  const int V = g.size();
  auto inf = Edge::INF;
  Weights dist(V, inf);
  prev.assign(V, -1);

  dist[s] = 0;
  std::priority_queue<Edge> pq;
  for (pq.emplace(-2, s, 0); !pq.empty();) {
    auto e = pq.top();
    pq.pop();
    if (prev[e.to] != -1) continue;
    prev[e.to] = e.from;
    for (const auto& f : g[e.to]) {
      if (dist[f.to] <= e.w + f.w) continue;
      pq.emplace(f.from, f.to, dist[f.to] = e.w + f.w);
    }
  }
  return std::move(dist);
}
Weights dijkstra(const Graph& g, int s) {
  std::vector<int> prev;
  return std::move(dijkstra(g, s, prev));
}
std::pair<Weight, Path> dijkstra(const Graph& g, int s, int t) {
  std::vector<int> prev;
  auto ws = dijkstra(g, s, prev);
  auto path = util::buildPath(t, prev);
  return std::move(std::make_pair(ws[t], std::move(path)));
}
}
}
}
//}}}

int sq(int x) {
  return x * x;
}

signed main() {
  while (int N = in()) {
    map<int, int> table;
    vec<int> B(N), X(N), Y(N);
    REP(i, N) {
      B[i] = in();
      X[i] = in();
      Y[i] = in();
      table[B[i]] = i;
    }
    orliv::Graph G(N);
    REP(i, N) {
      REP(j, N) {
        if (i == j) continue;
        double d = sqrt(sq(X[i] - X[j]) + sq(Y[i] - Y[j]));
        if (d <= 50) { G[i].emplace_back(i, j, d); }
      }
    }
    int M = in();
    REP(i, M) {
      int s = in(), g = in();
      auto result = orliv::graph::shortest_path::dijkstra(G, table[s], table[g]);
      auto cost = result.first;
      auto route = result.second;
      if (orliv::graph::Edge::INF <= cost + 1) {
        cout << "NA";
      } else {
        REP(i, route.size()) {
          if (i) cout << " ";
          cout << B[route[i]];
        }
      }
      cout << endl;
    }
  }
  return 0;
}

C++: #include<iostream>
#include<cstring>
#include<queue>
#include<cmath>
#include<stack>
using namespace std;
#define INF 1e10
#define EPS 1e-6
#define EQ(a,b) (fabs((a)-(b))<EPS)

double dist[1000][1000];
int id[1000],x[1000],y[1000];

double Distance(int i,int j){
	return sqrt((double)(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}


int main(){
	int n;
	while(cin>>n&&n){
		for(int i=0;i<n;i++)cin>>id[i]>>x[i]>>y[i];
		for(int i=0;i<n;i++)for(int j=0;j<n;j++){
			double d=Distance(i,j);
			dist[i][j]=(d<=50?d:INF);
		}
		for(int k=0;k<n;k++)for(int i=0;i<n;i++)for(int j=0;j<n;j++)
			dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
		int m;
		cin>>m;
		for(int i=0;i<m;i++){
			int s,g;
			cin>>s>>g;
			s--;g--;
			if(dist[s][g]==INF){
				cout<<"NA\n";
				continue;
			}
			stack<int> st;
			int v=g;
			while(v!=s){
				for(int i=0;i<n;i++){
					if(i==v)continue;
					if(EQ(dist[s][v],dist[s][i]+Distance(i,v))){
						st.push(v);
						v=i;
						break;
					}
				}
			}
			cout<<id[s];
			while(!st.empty()){
				cout<<' '<<id[st.top()];
				st.pop();
			}
			cout<<endl;
		}
	}
	return 0;
}