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 <sstream>
#include <vector>
#include <map>
#include <cmath>
using namespace std;

#define DIS(x,y) (sqrt((double)(x)*(double)(x)+(double)(y)*(double)(y)))
#define INF 999999


vector<double> dist;	// ÅZ£ði[·éXg
vector<int> route;	  // ÅZ[gði[·éXg

void Dijkstra(vector<vector<double> >& connect, int start)
{
	// m[hÌæ¾
	int node_n = connect.size();


	// ÅZ£ði[·éXgðINFÅú»(n_Í0)
	dist.clear();
	dist.resize(node_n);
	for(int i=0; i<node_n; i++) { dist[i] = INF; }
	dist[start] = 0;
	
	// ÅZ[gði[·éXgðINFÅú»(n_Í-1)
	route.clear();
	route.resize(node_n);
	for(int i=0; i<node_n; i++) { route[i] = INF; }
	route[start] = -1;
	
	// ÅZ£mèóÔð\·XgÌì¬
	vector<int> deci(node_n);
	for(int i=0; i<node_n; i++) { deci[i] = false; }

	// »ÝÌm[h
	int now_node;
	
	while(1)
	{
		// Å¬£Ìm[hðæ¾·é
		// úÌÅ¬lÍINFæèå«­
		now_node = -1;
		double shortest  = INF+1;
		for(int i=0; i<node_n; i++)
		{
			if(!deci[i] && shortest>dist[i])
			{
				shortest = dist[i];
				now_node = i;
			}
		}
		
		// ·×ÄÏÝÈç[vð²¯é
		if(now_node == -1) { break; }
		// »ÝÌm[hðmèÏÝÉ
		deci[now_node] = true;
		
		// »ÝÌm[h©çÌ¼Ì_Ì£ðvZ
		// mèÏÝÅ éi©gÅ éðÜÞjÚ±ªINFÅ éêÍ³
		// em[hÌÅZ£ðvZÊ©³ÌlÌ¬³¢ûÉÝè
		// ÅZHÅ Á½ê¼ÌÅZ[gðXV·é
		for(int i=0; i<node_n; i++)
		{
			if(connect[now_node][i]!=INF && !deci[i])
			{
				double tmp = dist[now_node]+connect[now_node][i];
				if(dist[i]>tmp)
				{
					dist[i] = tmp;
					route[i] = now_node;	
				}
			}
		}
	}

	return;
}

int main()
{
	stringstream ss;
	
	// üÍ
	int n,m,tmp;
	while(1)
	{
		cin >> n;
		if(n==0) { break; }	// 0ÅI¹

		// üÍirÌXgAÚ®Xgj
		// rÔÌÎMAPàì¬
		vector<vector<int> > b_data(n,vector<int>(3));
		map<int,int> bn_list;
		for(int i=0; i<n; i++)
		{
			cin >> b_data[i][0] >> b_data[i][1] >> b_data[i][2];
			bn_list[b_data[i][0]] = i;
		}
		cin >> m;
		vector<vector<int> > m_data(m,vector<int>(2));
		for(int i=0; i<m; i++)
		{
			cin >> m_data[i][0] >> m_data[i][1];
		}
		
		// AóÔð\·zñÌì¬ (AsÂ=INFA©gÆÌ£=0)
		vector<vector<double> > c_data(n,vector<double>(n));
		for(int i=0; i<n; i++)
		{
			for(int j=0; j<n; j++)
			{
				double dis = DIS(b_data[i][1]-b_data[j][1],b_data[i][2]-b_data[j][2]);
				if(dis <= 50)	{ c_data[i][j] = dis; }
				else		{ c_data[i][j] = INF; }
			}		
		}

		// Ú®f[^ÉvZ n_ðI_ðüêÖ¦
		// iHõÌÆ«­È¢Ù¤ÖÆ¾ÇêÎ
		// tÉÈéªüêÖ¦Ä¢é½ßûüÉÈé
		for(int i=0; i<m; i++)
		{
			Dijkstra(c_data,bn_list[m_data[i][1]]);
			
			int m_node = bn_list[m_data[i][0]];
			if(route[m_node] == INF)
			{
				ss << "NA" << endl;
			}
			else
			{
				for(; route[m_node]!=-1; m_node=route[m_node])
				{
					ss << b_data[m_node][0] << " ";
				}
				ss << b_data[m_node][0] << endl;
			}
		}
	}

	cout << ss.str();

	return 0;
}

C++: #include <cstdio>
#include <cmath>
#include <cstdint>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <utility>

std::vector<size_t> nya(size_t s, size_t t, std::vector<std::vector<size_t>> const& via) {
  if (s == t) return {s};
  size_t k = via[s][t];
  if (k == s) return {s, t};

  auto former = nya(s, k, via);
  auto latter = nya(k, t, via);
  if (former.back() == latter[0])
    former.pop_back();

  former.insert(former.end(), latter.begin(), latter.end());
  return former;
}

int testcase_ends() {
  size_t n;
  scanf("%zu", &n);
  if (n == 0) return 1;

  double inf = 1e9;
  std::vector<std::vector<double>> g(n, std::vector<double>(n, inf));
  for (size_t i = 0; i < n; ++i) g[i][i] = 0;

  std::vector<double> x(n), y(n);
  for (size_t i = 0; i < n; ++i) {
    size_t b;
    scanf("%zu", &b);
    --b;
    scanf("%lf %lf", &x[b], &y[b]);
  }
  for (size_t i = 0; i < n; ++i) {
    for (size_t j = 0; j < n; ++j) {
      double dx = x[i]-x[j];
      double dy = y[i]-y[j];
      if (dx*dx + dy*dy > 50*50) continue;
      g[i][j] = g[j][i] = hypot(dx, dy);
    }
  }

  std::vector<std::vector<size_t>> via(n, std::vector<size_t>(n));
  for (size_t i = 0; i < n; ++i)
    for (size_t j = 0; j < n; ++j)
      via[i][j] = i;

  for (size_t k = 0; k < n; ++k)
    for (size_t i = 0; i < n; ++i)
      for (size_t j = 0; j < n; ++j) {
        if (g[i][j] > g[i][k] + g[k][j]) {
          g[i][j] = g[i][k] + g[k][j];
          via[i][j] = k;
        }
      }

  size_t m;
  scanf("%zu", &m);

  for (size_t i = 0; i < m; ++i) {
    size_t s, t;
    scanf("%zu %zu", &s, &t);
    --s;
    --t;
    if (g[s][t] >= inf) {
      puts("NA");
      continue;
    }
    std::vector<size_t> res = nya(s, t, via);
    for (size_t j = 0; j < res.size(); ++j)
      printf("%zu%c", res[j]+1, j+1<res.size()? ' ':'\n');
  }
  return 0;
}

int main() {
  while (!testcase_ends()) {}
}