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"
using namespace std;

//#define int long long
#define DEBUG 0
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()
#define dump(o) if(DEBUG){cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) if(DEBUG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
using pii = pair<int, int>; using vi = vector<int>;
static const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
static const int MOD = (int)(1e9 + 7);


using Weight = int;
class Edge {
public:
	int s; //source
	int d; //destination
	Weight w; //weight
	Edge(int s = 0, int d = 0, Weight w = INF) : s(s), d(d), w(w) {};
	bool operator<(const Edge &e)const { return w < e.w; }
};
using Edges = vector<Edge>;
//???????????\: g[u].push_back(Edge(u, v, c));
//????????¨???????????????????????°??????????????\?????????????????????
using Graph = vector<Edges>;
using Array = vector<Weight>;
using Matrix = vector<Array>;

//

//?????¢?´¢, ??¢?´¢???, ??¢?´¢???
enum { WHITE, GRAY, BLACK };
//???????§?????????????(???????????????) Single Source Shortest Path
//Dijkstra O( |E|log|V| )
//dist: ?§????????????????????????§??????????????¢
//?????????: ???????????¨????????????(??????-1)
vector<int> dijkstra(const Graph &g, int s, vector<Weight> &dist) {
	typedef tuple<Weight, int, int> State; //?§?????????????????°?????????? ??? ???
	priority_queue<State, vector<State>, greater<State> >PQ;
	int n = g.size();
	vector<int> color(n, WHITE);
	vector<int> prev(n, -1);
	dist.assign(n, INF); //distance
	dist[s] = 0; PQ.emplace(0, s, -1); color[s] = GRAY; //?§????
	while (!PQ.empty()) {
		Weight d; int v; int u;
		tie(d, v, u) = PQ.top(); PQ.pop(); //dist???????°??????¨??????????´????????????????
		if (dist[v] < d) continue; //?????§???????????§???????????°??????
		color[v] = BLACK;
		prev[v] = u;
		for (auto &e : g[v]) { //??£??\????????????????????¨????????????		
			if (color[e.d] == BLACK)continue; //??¢?´¢????????????
			if (dist[e.d] > dist[v] + e.w) {
				dist[e.d] = dist[v] + e.w;
				PQ.emplace(dist[e.d], e.d, v);
				color[e.d] = GRAY;
			}
		}
	}
	return prev;
}

//?§?????????????????????§??????????????????
//???????????????????????°?????????????§??????????????????§?????????????????¢????????????
//?????¨???????????´???????????????: vector<int>()
vector<int> getPath(int s, int g, vector<int> prev) {
	vector<int> path;
	path.emplace_back(g);
	for (int i = g; i != s; ) {
		if (i == -1)return vector<int>();
		path.emplace_back(i = prev[i]);
	}
	reverse(path.begin(), path.end());
	return path;
}

class B {
public:
	int b, x, y;
};

int d(B B1, B B2) {
	return (B1.x - B2.x)*(B1.x - B2.x) + (B1.y - B2.y)*(B1.y - B2.y);
}

signed main() {
	for (int n; cin >> n&&n;) {
		Graph g(n);
		vector<B> Bs(n);
		rep(i, 0, n) {
			cin >> Bs[i].b >> Bs[i].x >> Bs[i].y;
			Bs[i].b--;
		}
		rep(i, 0, n)rep(j, 0, n) {
			if (i == j)continue;
			int dd = d(Bs[i], Bs[j]);
			if (dd > 50 * 50)continue;
			g[Bs[i].b].emplace_back(Bs[i].b, Bs[j].b, dd);
		}
		int m; cin >> m;
		rep(i, 0, m) {
			int start, goal; cin >> start >> goal;
			start--, goal--;
			vector<Weight> dist;
			vector<int> prev = dijkstra(g, start, dist);
			vector<int> path = getPath(start, goal, prev);
			if (path.size() == 0) {
				cout << "NA" << endl;
				continue;
			}
			cout << path[0] + 1;
			rep(j, 1, path.size())cout << " " << path[j] + 1;
			cout << endl;
		}
	}
	return 0;
}

C++: #include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <cstring>
#include <deque>
#include <cstdio>
#include <cmath>
#include <complex>
#include <iostream>
#include <iterator>

using namespace std;

#define reep(i,f,t) for(int i=f ; i<int(t) ; ++i)
#define rep(i,n) reep(i, 0, n) 

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

struct Edge
{
	int src, dst;
	double weight;
	Edge(int src, int dst, double weight) : src(src), dst(dst), weight(weight) {}

	bool operator< (const Edge& e)const
	{
		return weight != e.weight ? weight > e.weight :
			src != e.src ? src < e.src : dst < e.dst;
	}
};

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

int main()
{
	int n;
	while(scanf("%d", &n), n){
		map<int, int> id;
		vector<pii> pts(n);
		vi preid(n);
		rep(i, n){
			int b, x, y;
			scanf("%d%d%d", &b, &x, &y);
			pts[i] = pii(x, y);
			preid[i] = b;
			id[b] = i;
		}
		
		Graph G(n);
		rep(i, n) rep(j, i){
			pii diff(pts[i].first - pts[j].first, pts[i].second - pts[j].second);
			int dist = diff.first*diff.first + diff.second*diff.second;
			if(dist <= 2500){
				double w = sqrt(dist);
				G[i].push_back(Edge(i, j, w));
				G[j].push_back(Edge(j, i, w));
			}
		}
		
		int m;
		scanf("%d", &m);
		rep(i, m){
			int s, g;
			scanf("%d%d", &s, &g);
			s = id[s];
			g = id[g];
			
			vi pre(n, -1);
			priority_queue<Edge> Q;
			Q.push(Edge(-2, s, 0.0));
			while(!Q.empty()){
				Edge e = Q.top();
				Q.pop();
				if(pre[e.dst] != -1)
					continue;
				pre[e.dst] = e.src;
				if(e.dst == g)
					break;
				
				rep(j, G[e.dst].size()){
					Q.push(Edge(e.dst, G[e.dst][j].dst, e.weight + G[e.dst][j].weight));
				}
			}
			
			if(pre[g] == -1)
				puts("NA");
			else{
				vi path;
				int now = g;
				while(now != s){
					now = pre[now];
					path.push_back(now);
				}
				
				for(int j=path.size()-1; j>=0; --j)
					printf("%d ", preid[path[j]]);
				printf("%d\n", preid[g]);
			}
		}
	}

	return 0;
}