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 <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
//#include <utility>
#include <set>
#include <iostream>
//#include <memory>
#include <string>
#include <vector>
#include <algorithm>
//#include <functional>
#include <sstream>
//#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
//#include <cctype>
#include <cstring>
//#include <ctime>
#include <iterator>
#include <bitset>
//#include <numeric>
//#include <list>
//#include <iomanip>

#if __cplusplus >= 201103L
#include <array>
#include <tuple>
#include <initializer_list>
#include <unordered_set>
#include <unordered_map>
#include <forward_list>

#define cauto const auto&
#else

#endif

using namespace std;


namespace{
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
    v.assign(a, vector<T>(b, t));
}

template <class F, class T>
void convert(const F &f, T &t){
    stringstream ss;
    ss << f;
    ss >> t;
}


#define reep(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) reep((i),0,(n))
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define F first
#define S second
#define mkp make_pair
#define RALL(v) (v).rbegin(),(v).rend()


#define MOD 1000000007LL
#define EPS 1e-8
#define prev S.F
#define now S.S
static const int INF=1<<24;
typedef complex<double> P;
void mainmain(){
	int n;
	while(cin>>n,n){
		vector<P> biru;
		vint id(n);
		map<int,int>  id2;
		rep(i,n){
			int a,b,c;
			cin>>a>>b>>c;
			// cout<<a<<" "<<b<<" "<<c<<endl;
			id[i]=a;
			id2[a]=i;
			biru.PB(P(b,c));
		}
		vector<vector<pair<int,double>>> vv(n);
		rep(i,n){
			rep(j,n){
				if(i==j) continue;
				if(50.0-abs(biru[i]-biru[j])>-EPS){
					vv[j].PB(mkp(i,abs(biru[i]-biru[j])));
					// vv[i].PB(mkp(j,abs(biru[i]-biru[j])));
				}
			}
		}
		// rep(i,n){
			// cout<<i<<endl;
			// rep(j,vv[i].size()){
				// cout<<vv[i][j].F<<" "<<vv[i][j].S<<endl;
			// }
		// }
		// cout<<endl;
		int m;
		cin>>m;
		rep(i,m){
			vector<pair<double,int> >  ans(n,mkp(-1.0,-1));
			priority_queue<pair<double,pii> > pq;
			int s,g;
			cin>>s>>g;
			if(s==g){
				cout<<s<<endl;
				continue;
			}
			// cout<<s<<" "<<g<<endl;
			// cout<<id2[s]<<" "<<id2[g]<<endl;
			pq.push(mkp(0.0,mkp(id2[s],id2[s])));
			while(!pq.empty()){
				pair<double,pii> top=pq.top();
				pq.pop();
				if(ans[top.now].S!=-1) continue;
				ans[top.now]=mkp(-top.F,top.prev);
				rep(i,vv[top.now].size()){
					if(ans[vv[top.now][i].F].S==-1){
						pq.push(mkp(top.F-vv[top.now][i].S,mkp(top.now,vv[top.now][i].F)));
					}
				}
			}
			// cout<<"------"<<endl;
			// rep(i,n){
				// cout<<ans[i].F<<" "<<ans[i].S<<endl;
			// }
			if(ans[id2[g]].S==-1){
				cout<<"NA\n";
				continue;
			}
			vint ret;
			int t=id2[g];
			while(t!=id2[s]){
				ret.PB(id[t]);
				t=ans[t].S;
			}
			ret.PB(s);
			reverse(ALL(ret));
			rep(i,ret.size()){
				if(i) cout<<" ";
				cout<<ret[i];
			}
			cout<<endl;
		}
	}
}



}
main() try{
    mainmain();
}
catch(...){
}

C++: #include <iostream>
#include <algorithm>
#include <cassert>
#include <cctype>
#include <complex>
#include <cstdio>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;

#define INF 1e9
#define rep(i,n) for(int i=0;i<n;i++)
struct edge{int to;double cost;};
typedef pair<int,int> P;

int V,n,m,x[1001],y[1001],S,G,B,X,Y,prv[1001];
double d[1001];
vector<edge> g[1001];

int main(){
	while(cin>>n&&n){
		fill(x,x+1001,-100);
		fill(y,y+1001,-100);
		rep(i,1001)g[i].clear();
		rep(i,n){cin>>B>>X>>Y;x[B]=X;y[B]=Y;}
		rep(i,1001)rep(j,1001)if(i!=j&&(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])<=2500){
			edge e;
			e.to=j;e.cost=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
			g[i].push_back(e);
			e.to=i;
			g[j].push_back(e);
		}
		cin>>m;
		rep(h,m){
			cin>>S>>G;
			priority_queue<P,vector<P>,greater<P> > q;
			fill(d,d+1001,INF);
			fill(prv,prv+1001,-1);
			d[S]=0;
			q.push(P(0,S));
			while(!q.empty()){
				P p=q.top();q.pop();
				int v=p.second;
				if(d[v]<p.first)continue;
				rep(i,g[v].size()){
					edge e=g[v][i];
					if(d[e.to]>d[v]+e.cost){
						d[e.to]=d[v]+e.cost;
						q.push(P(d[e.to],e.to));
						prv[e.to]=v;
					}
				}
			}
			//cout<<prv[S]<<endl;
			//rep(i,1001)if(prv[i]!=-1)cout<<i<<" "<<prv[i]<<endl;
			if(d[G]==INF)cout<<"NA"<<endl;
			else{
				//cout<<d[G]<<endl;
				vector<int> path;
				for(;G!=-1;G=prv[G])path.push_back(G);
				reverse(path.begin(),path.end());
				rep(i,path.size())cout<<path[i]<<(i<path.size()-1?" ":"\n");
			}
		}
	}
}