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	<vector>
#include	<map>
#include	<iterator>
#include	<utility>
#include	<functional>
#include	<limits>
#include	<cmath>

template< typename T >
class	box
{
	private:
		typedef	std::size_t	I;
		T*	data;
			I	m, n;
	public:
		typedef	T*	iterator;
		typedef	const T*	const_iterator;
		typedef	std::reverse_iterator<iterator>	reverse_iterator;
		typedef	std::reverse_iterator<const_iterator>	const_reverse_iterator;
		
		box( I m_, I n_ )	: m(m_), n(n_), data( new T[m_*n_] ){}
		box()	: data(0), n(0), m(0){}
		box( const box& obj )	: m(obj.m), n(obj.n), data( new T[obj.m*obj.n] )
		{
			std::copy( obj.begin(), obj.end(), begin() );
		}
		box&	operator=( const box& obj )
		{
			delete[]	data;
			m = obj.m, n = obj.n;
			data	= new	T[m*n];
			std::copy( obj.begin(), obj.end(), begin() );
		}
		~box(){ delete[]	data; }
		T&	operator()( I i, I j ){ return	data[i*n+j]; }
		const T&	operator()( I i, I j )const{ return	data[i*n+j]; }
		
		iterator	begin()	{ return	data; }
		const_iterator	begin()const	{ return	data; }
		iterator	end()	{ return	data + m*n; }
		const_iterator	end()const	{ return	data + m*n; }
		reverse_iterator	rbegin()	{ return	reverse_iterator(data + m*n ); }
		const_reverse_iterator	rbegin()const	{ return	const_reverse_iterator(data + m+n); }
		reverse_iterator	rend()	{ return	reverse_iterator(data); }
		const_reverse_iterator	rend()const	{ return	const_reverse_iterator(data); }

		void	print()
		{
			for( int i=0 ; i<m ; i++ )
			{
				for( int j=0 ; j<n ; j++ )	std::cout << operator()(i,j);
				std::cout << std::endl;
			}
		}
};


template< typename T >
struct	minpath
{
	std::vector<int>	nodes;
	T	weight;
};

template< typename T, typename FJ, typename FC >
class	AM	//Adjacency Matrix
{
	private:
		typedef	minpath<T>	mp;
		box<mp>	arr;
		const FC	compare;
		const FJ	join;
		const int	N;

	public:
		AM( int N_, T inf, T zero, FJ join_ = std::plus<T>(), FC compare_ = std::less<T>() )
			: N(N_), arr(N_,N_), compare(compare_), join(join_)
		{
			for( typename box<mp>::iterator it = arr.begin(); it != arr.end() ; it++ )	it->weight	= inf;
			for( int i=0 ; i<N ; i++ )
			{
				const mp	temp	= { std::vector<int>(0), zero };
				arr(i,i)	= temp;
			}
		}
		
		void	makeedge( int i, int j, T weight )
		{
			std::vector<int>	ij(1);
			ij[0]	= j;
			mp	temp	= { ij, weight };
			arr(i,j)	= temp;
		}
		
		void	optimize()
		{
			using namespace	std;
			for( int k=0 ; k<N ; k++ )	for( int i=0 ; i<N ; i++ )	for( int j=0 ; j<N ; j++ )
			{
				T	joint	= join( arr(i,k).weight, arr(k,j).weight );
				if( compare( joint, arr(i,j).weight ) )
				{
					arr(i,j).weight	= joint;
					arr(i,j).nodes.resize( arr(i,k).nodes.size() + arr(k,j).nodes.size() );
					vector<int>::iterator	temp	= copy(
						arr(i,k).nodes.begin(),
						arr(i,k).nodes.end(),
						arr(i,j).nodes.begin()
					);
					copy(
						arr(k,j).nodes.begin(),
						arr(k,j).nodes.end(),
						temp
					);
				}
			}
		}
		
		const mp&	operator()( int i, int j )const	{ return	arr(i,j);	}
		
		void	print()
		{
			using namespace	std;
			for( int i=0 ; i<N ; i++ )	for( int j=0 ; j<N ; j++ )
			{
				cerr << i << "," << j << ":\t";
				for( vector<int>::const_iterator it = arr(i,j).nodes.begin() ; it != arr(i,j).nodes.end() ; it++ )
					cerr << *it << ' ';
				cerr << endl;
			}
			cerr << endl;
		}
};


struct	weight
{
	bool	isinf;
	int	num;
	double	dist;
};

const weight	inf	= { true, std::numeric_limits<int>::max() , std::numeric_limits<double>::infinity() };
const weight	zero	= { false, 0, 0 };

struct	Compare
{
	inline bool	operator()( const weight& lhs, const weight& rhs )	const
	{
		if( lhs.isinf )	return	false;
		if( rhs.isinf )	return	true;
		if( lhs.num < rhs.num )	return	true;
		if( lhs.num > rhs.num )	return	false;
		if( lhs.dist < rhs.dist )	return	true;
		return	false;
	}
}	compare;


struct	Join
{
	typedef	minpath<weight>	mp;
	inline	weight	operator()( const weight& lhs, const weight& rhs )	const
	{
		weight	ret;
		ret.isinf	= lhs.isinf || rhs.isinf;
		ret.num	= lhs.num + rhs.num;
		ret.dist	= lhs.dist + rhs.dist;
		return	ret;
	}
}	join;


inline double	ED( double x, double y )	//Eucleaden Distance
{
	return	std::sqrt( x*x + y*y );
}


struct	bldg
{
	int	id, x, y;
};

int	main()
{
	using namespace	std;
	for(;;)
	{
		int	N;
		cin	>> N;
		if( N == 0 )	return	0;
		bldg*	bldgs	= new	bldg[N];
		map<int,int>	id;
		for( int i=0 ; i<N ; i++ )
		{
			cin	>> bldgs[i].id >> bldgs[i].x >> bldgs[i].y;
			id.insert( make_pair( bldgs[i].id, i ) );
		}
		
		AM<weight,Join,Compare>	obj( N, inf, zero, join, compare );
		for( int i=0 ; i<N ; i++ )	for( int j=0 ; j<N ; j++ )
		{
			if( i == j )	continue;
			double	dist	= ED( bldgs[i].x - bldgs[j].x, bldgs[i].y - bldgs[j].y );
			if( dist > 50 )	continue;
			weight	w	= { false, 1, dist };
			obj.makeedge( i, j, w );
			obj.makeedge( j, i, w );
		}
		
		obj.optimize();
		
		int	M;
		cin	>> M;
		for( int k=0 ; k<M ; k++ )
		{
			int	s, g;
			cin	>> s >> g;
			s	= id[s],	g	= id[g];
			if( obj(s,g).weight.isinf )
			{
				cout << "NA" << endl;
				continue;
			}
			const vector<int>&	nodes	= obj(s,g).nodes;
			
			cout << bldgs[s].id;
			for( vector<int>::const_iterator it = nodes.begin() ; it != nodes.end() ; it++ )
				cout << ' ' << bldgs[*it].id;
			cout << endl;
		}		
		delete[]	bldgs;
	}
}