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 <iostream>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cmath>

using namespace std;
typedef long long ll;
typedef pair<double, ll> P;

#define reps(i, s, e) for (ll i = s; i < e; ++i)
#define rep(i, n) reps(i, 0, n)
#define rreps(i, s, e) for (ll i = e-1; i >= s; --i)
#define rrep(i, n) rreps(i, 0, n)

// ノード
struct Node {
    ll node, x, y;
    Node(ll _node=0, ll _x=0, ll _y=0):node(_node), x(_x), y(_y) {}

    void entry(ll _node, ll _x, ll _y) {
        node = _node;
        x = _x;
        y = _y;
    }
};

inline ll dis(const Node& n1, const Node& n2) {
    return (n1.x-n2.x)*(n1.x-n2.x) + (n1.y-n2.y)*(n1.y-n2.y);
}

// エッジ
struct oEdge {
    double cost;
    ll to;
    oEdge(double _c=0, ll _to=0): cost(_c), to(_to) {}
};

bool operator<(const oEdge& e1, const oEdge& e2) {
    return e1.cost < e2.cost;
}

class Graph {
public:
    // ノードの数
    ll node;
private:
    // ノード
    vector<Node> _V;
    // 移動可能なエッジ
    vector< vector<oEdge> > _E;

public:
    Graph(const vector<Node>& V):node(V.size()), _V(V) {
        _E.resize(node);

        // ノードiとノードjの距離が2500未満のとき追加
        rep(i, node) rep(j, i) {
            ll d = dis(_V[i], _V[j]);
            if (d > 2500) continue;
            double cost = sqrt(d);
            oEdge e(cost, _V[j].node);
            _E[_V[i].node].push_back(e);
            e.to = _V[i].node;
            _E[_V[j].node].push_back(e);
        }
    }

    void calc_path(ll s, ll g) {
        double d_inf = 100000;

        // キュー
        priority_queue<P, vector<P>, greater<P> > que;
        que.push(P(0., s));

        // 最短コスト
        vector<double> d(node, d_inf);
        d[s] = 0.;

        // 1つ前のノード
        vector<ll> prev_node(node, -1);
        
        // sから近い順に取り出す
        while (!que.empty()) {
            // ノードv
            P pair = que.top();
            que.pop();
            ll v = pair.second;
            if (pair.first > d[v]) continue;

            // v_toへの最短の行きかたを探索
            rep(i, _E[v].size()) {
                oEdge e = _E[v][i];

                if (d[e.to] > d[v] + e.cost) {
                    d[e.to] = d[v] + e.cost;
                    prev_node[e.to] = v;
                    que.push(P(d[e.to], e.to));
                }               
            }
        }

        
        if (d[g]==d_inf) cout << "NA\n";
        else {
            vector<ll> path;
            path.push_back(g);
    
            while(true) {
                ll n = prev_node[path.back()];
                path.push_back(n);
                if (n == s) break;
            }
            reverse(path.begin(), path.end());
            rep(i, path.size()) {
                cout << path[i]+1;
                if (i < path.size()-1) cout << " ";
                else cout << "\n";
            }
        }
    }
};

int main() {
    // グラフ
    vector<Graph> Gs;
    // 移動のスタートとゴール
    vector< vector< pair<ll, ll> > > SGs;

    ll n;
    while(cin >> n && n != 0) {
        vector<Node> v(n);
        rep(i, n) {
            ll node, x, y;
            cin >> node >> x >> y;
            v[i].entry(node-1, x, y);
        }
        Gs.push_back(Graph(v));

        ll m;
        cin >> m;
        vector< pair<ll, ll> > sg(m);
        rep(i, m) {
            ll s, g;
            cin >> s >> g;
            sg[i] = make_pair(s-1, g-1);
        }
        SGs.push_back(sg);
    }

    rep(graph, Gs.size()) {
        rep(i, SGs[graph].size()) {
            // スタート，ゴール
            ll s = SGs[graph][i].first;
            ll g = SGs[graph][i].second;
            Gs[graph].calc_path(s, g);
        }
    }
}