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 <cstdio>
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <string>
#include <map>
#include <algorithm>
#include <cmath>
#define rep(i,n) for(int i=0; i<n; ++i)
using namespace std;
typedef pair<int,int> P;

const double INF = 10000000;
struct Node{
  int x,y;
  vector<int> to;
  vector<double> cost;
  vector<int> root;
};
int N,M;
int V;
Node G[1001];
int d[1001];
bool visit[1001];

inline double dist(Node a, Node b){
  return sqrt((double)((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y)));
}

void init(){
  for(int i=1; i<=1001; ++i){
    G[i-1].root.clear();
    d[i-1] = INF;
    visit[i-1] = false;
  }
}
void makeEdge(){
  for(int i=1; i<=N; ++i){
    G[i].to.clear();
    G[i].cost.clear();
    for(int j=1; j<=N; ++j){
      if(i == j) continue;
      if(dist(G[i],G[j]) <= 50){
//        printf("%d -> %d dist::%d \n",i,j,dist(G[i],G[j]));
        G[i].to.push_back(j);
        G[i].cost.push_back(dist(G[i],G[j]));
      }
    }
//    printf("%d\n",G[i].to.size());
  }
}

void dijkstra(int e){
  int cnt = 1;
  while(cnt <= N){
    double m = INF;
    vector<int> m_r;
//    printf("cnt:%d\n",cnt);
    for(int i=1; i<=N; ++i){
      if(visit[i] == false) continue;
      for(int j=0;j<G[i].to.size();++j){
        if(visit[G[i].to[j]] == true) continue;
//        printf("%d->%d\n",i,G[i].to[j]);
        if(d[i] + G[i].cost[j] < m){
          m = d[i] + G[i].cost[j];
          m_r.assign(G[i].root.begin(), G[i].root.end());;
          m_r.push_back(G[i].to[j]);
          
        }
      }
    }
    if(m == INF) break;
    G[m_r.back()].root.assign(m_r.begin(), m_r.end());
    d[m_r.back()] = m;
    visit[m_r.back()] = true;
//    printf("%d  (cost:%lf)\n",m_r.back(),m);

    if(m_r.back() == e){
      cout << G[m_r.back()].root[0];
      for(int i=1; i<G[m_r.back()].root.size(); ++i){
        cout << " " << G[m_r.back()].root[i];
      }
      cout << endl;
      return;
    }
    cnt++;
  }
  cout << "NA" << endl;
  return;
}

int main(){
  while(cin >> N && N){
    for(int i=1; i<=N; ++i){
      int id;
      cin >> id;
      cin >> G[id].x >> G[id].y;
    }
    makeEdge();
    
    cin >> M;
    
    for(int i=1; i<=M; ++i){
      init();
      int s,e;
      cin >> s >> e;
      visit[s] = true;
      d[s] = 0;
      G[s].root.push_back(s);
      dijkstra(e);
    }
    
  }
  return 0;
}

C++: #define _USE_MATH_DEFINES
#include <iostream>
#include <sstream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>

using namespace std;

typedef long long ll;
typedef pair<int,int> P;

static const double eps = 10e-6;

struct Edge{
	int b;
	int x;
	int y;
};

vector<int> get_path(int t,int* prev){
	vector<int> path;
	for(; t!=-1; t = prev[t]) path.push_back(t);
	reverse(path.begin(),path.end());
	return path;
}

vector<int> dijkstra(int src,int dst, const vector<Edge>& edge){
	
	double d[1001];
	int prev[1001];
	bool used[1001];

	fill((double*)d,(double*)d+1001,10000000.0);
	fill((bool*)used,(bool*)used+1001,false);
	fill((int*)prev,(int*)prev+1001,-1);

	d[src] = 0.0;	

	while(true){

		int v = -1;
		for(int u=0;u<edge.size();u++){
			if(!used[u] && (v == -1 || d[u] < d[v])) v = u;
		}

		if(v == -1) break;
		used[v] = true;

		int srcX = edge[v].x;
		int srcY = edge[v].y;

		for(int u=0;u<edge.size();u++){
			if(u==v) continue;
			double cost = sqrt((double)(edge[u].x - srcX) * (double)(edge[u].x - srcX)
				+ (double)(edge[u].y - srcY) * (double)(edge[u].y - srcY));
			if(cost > 50.0) continue;

			if(d[u] > d[v] + cost){
				d[u] = d[v] + cost;
				prev[u] = v;
				//printf("u:%d v:%d\n",u+1,v+1);
			}
		}
	}
/*
	for(int i=0;i<edge.size();i++){
		printf("d[%d]=%d ",i+1,d[i]);
	}
	cout << endl;
*/
	return get_path(dst,prev);
}

int main(){
	string str;

	int n;
	while(~scanf("%d",&n)){
		if(n==0) break;
		vector<Edge> edge;
		for(int i=0;i<n;i++){
			int b,x,y;
			scanf("%d %d %d",&b,&x,&y);
			Edge e = {b,x,y};
			edge.push_back(e);
		}
		int m;
		scanf("%d",&m);

		for(int i=0;i<m;i++){
			int src,dst;
			scanf("%d %d",&src,&dst);
			int src_idx,dst_idx;
			for(int i=0;i<edge.size();i++){
				if(edge[i].b == src){
					src_idx = i;
				}
				if(edge[i].b == dst){
					dst_idx = i;
				}
			}

			vector<int> route = dijkstra(src_idx,dst_idx,edge);

			if(route[0] == src_idx && route[route.size()-1] == dst_idx){
				for(int j=0;j<route.size();j++){
					printf("%d%s",edge[route[j]].b,j == route.size() -1 ? "\n" : " ");
				}
			}
			else cout << "NA" << endl; 
		}
	}
}