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++: // #155
// 経路は未実装

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

#define sqr(x) (x)*(x)

using namespace std;

const int Size = 1100;
const int Limit = 999999;

typedef struct {
  int x;
  int y;
} Points;

int N; // # of Building
int M; // # of Move
Points Building[Size+1]; // 配列の大きさは限界より大きくする
int Ans[Size+1][Size+1];
double d[Size+1][Size+1];

void solve(void) {
  for(int k=1; k<N+1; k++) {
    for(int i=1; i<N+1; i++) {
      for(int j=1; j<N+1; j++) {
	if(d[i][j] > d[i][k]+d[k][j]) {
	  d[i][j] = d[i][k]+d[k][j];
	  Ans[i][j]=Ans[i][k];
	}
      }
    }
  }
}

int main(void) {

  while(1) {
    cin>>N;
    if(N==0) {
      break;
    }
    for(int i=0; i<N; i++) {
      Building[i].x=Building[i].y=Limit;
    }
    for(int i=0; i<N; i++) {
      int tmp;
      cin>>tmp;
      cin>>Building[tmp].x;
      cin>>Building[tmp].y;
      Ans[tmp][tmp]=tmp;
    }

    for(int i=1; i<Size+1; i++) {
      for(int j=1; j<Size+1; j++) {
	d[i][j]=hypot((Building[i].x-Building[j].x), (Building[i].y-Building[j].y));
	if(d[i][j]>50.0 || Building[i].x==Limit || Building[j].x==Limit) {
	  d[i][j]=Limit;
	}
        Ans[i][j]=j;
      }
    }

    //cout<<d[1][3]<<" "<<d[3][9]<<" "<<d[9][20]<<" "<<d[20][11]<<" "<<d[11][6]<<" "<<d[6][22]<<endl;

    solve();

    //cout<<d[1][3]<<" "<<d[1][9]<<" "<<d[1][20]<<" "<<d[1][11]<<" "<<d[1][6]<<" "<<d[1][22]<<endl;

    cin>>M;
    for(int i=0; i<M; i++) {
      int from, to;
      cin>>from;
      cin>>to;
      if(d[from][to] == Limit) {
	cout<<"NA"<<endl;
      }
      else {
	cout<<from;
	while(from!=to) {
	  cout<<" "<<Ans[from][to];
	  from=Ans[from][to];
	}
	cout<<endl;
      }
    }
  }
}

C++: #include<bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef pair<int,double>P;
struct ed{int to;double co;};
ed edge;
int num[101],n,st,go,m,pre[101];
double x[101],y[101],d[101];
vector<ed>v[101];
int main(){
  while(cin>>n,n){
    map<int,int>m1,m2;
    r(i,101)v[i].clear();
    r(i,n)cin>>num[i]>>x[i]>>y[i],m1[num[i]]=i,m2[i]=num[i];
    r(i,n)r(j,n)if(i!=j){
      double dis=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
      edge.co=dis,edge.to=j;
      if(dis<=50)v[i].push_back(edge);
    }
    cin>>m;
    while(m--){
      memset(pre,-1,sizeof(pre));
      int stt,goo;
      cin>>stt>>goo;st=m1[stt];go=m1[goo];
      r(i,101)d[i]=1e9;
      d[st]=0;
      priority_queue<P,vector<P>,greater<P> >q;
      q.push(P(st,0));
      while(!q.empty()){
        P pp=q.top();q.pop();
        int tt=pp.first;
        double di=pp.second;
        if(d[tt]<di)continue;
        r(i,v[tt].size()){
          edge=v[tt][i];
          if(d[edge.to]>di+edge.co){
            pre[edge.to]=tt;
            d[edge.to]=di+edge.co;
            q.push(P(edge.to,di+edge.co));
          }
        }
      }
      if(d[go]==1e9)cout<<"NA"<<endl;
      else{
        vector<int>vv;
        for(;go!=-1;go=pre[go])vv.push_back(go);
        reverse(vv.begin(),vv.end());
        r(i,vv.size()){
          if(i)cout<<' ';
          cout<<m2[vv[i]];
        }
        cout<<endl;
      }
    }
  }
}

C++: #include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

typedef vector<int> L;
typedef pair<int,int> P;

class Node
{
public:
	L to;
	vector<double> co;
};

class Trl
{
public:
	int p;
	double c;
	L ord;
	Trl(int p, double c, L ord) : p(p), c(c), ord(ord) {}

	bool operator<(const Trl& t) const {
		return c > t.c;
	}
};

Node node[1000];
L dic;
vector<P> p;

pair<double, L> dijkstra(int s, int d)
{
	bool v[1000] = {0};
	priority_queue<Trl> q;
	q.push(Trl(s, 0.0, L()));
	while (!q.empty())
	{
		Trl t=q.top(); q.pop();
		if (v[t.p]) continue;
		v[t.p] = true;
		t.ord.push_back(t.p);

		if (t.p == d) 
			return pair<double, L>(t.c, t.ord);

		for (int i=0; i<node[t.p].to.size(); i++)
		{
			int next = node[t.p].to[i];
			if (v[next]) continue;

			q.push(Trl(next, t.c+node[t.p].co[i], t.ord));
		}

	}
	return pair<double, L>(-1.0, L());
}

int twd(P p1, P p2)
{
	return (p1.first-p2.first)*(p1.first-p2.first) + (p1.second-p2.second)*(p1.second-p2.second);
}

int rdic(int n)
{
	return find(dic.begin(), dic.end(), n) - dic.begin();
}

int main()
{
	int n;
	while (cin >> n, n)
	{
		dic.clear(); p.clear();
		memset(node, 0, sizeof(node));
		for (int i=0; i<n; i++)
		{
			int b, x, y;
			cin >> b >> x >> y;
			dic.push_back(b);
			p.push_back(P(x, y));
		}

		for (int i=0; i<n; i++)
		for (int j=i+1; j<n; j++)
		{
			int dd = twd(p[i], p[j]);
			if (dd > 2500) continue;
			node[i].to.push_back(j);
			node[i].co.push_back(sqrt((double)dd));
			node[j].to.push_back(i);
			node[j].co.push_back(sqrt((double)dd));
		}

		int m;
		cin >> m;

		while (m--)
		{
			int s, g;
			cin >> s >> g;
			pair<double,L> res = dijkstra(rdic(s), rdic(g));
			
			if (res.second.empty())
			{
				cout << "NA" << endl;
			}
			else
			{
				int s = res.second.size()-1;
				for (int i=0; i<s; i++)
					cout << dic[res.second[i]] << ' ';
				cout << dic[res.second[s]] << endl;
			}
		}
	}
	return 0;
}