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()
			}
		}
	}
}

Python: # -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0155

"""
import sys
from sys import stdin
from math import sqrt
input = stdin.readline


def dijkstra(s, G):
    BLACK, GRAY, WHITE = 0, 1, 2
    d = [float('inf')] * 101
    color = [WHITE] * 101
    p = [-1] * 101

    d[s] = 0
    while True:
        mincost = float('inf')
        # ??\??????????????§??????????????¨?????????????????????u???????????????
        for i in range(101):
            if color[i] != BLACK and d[i] < mincost:  # S????±???????????????????S??¨??\?¶?????????????????????????????????????????°???????????????????
                mincost = d[i]
                u = i  # u??????????????????ID
        if mincost == float('inf'):
            break
        color[u] = BLACK  # ?????????u???S????±???????????????´???
        for v in range(101):
            if color[v] != BLACK and G[u][v] != float('inf'):
                # v????????????????????????????????°??????S???????????£???u????????????????????????????????????????????°??????????????±??§??´??°??????
                if d[u] + G[u][v] < d[v]:
                    d[v] = d[u] + G[u][v]
                    p[v] = u
                    color[v] = GRAY
    return d, p


def main(args):
    while True:
        n = int(input())
        if n == 0:
            break

        G = [[float('inf')] * (100+1) for _ in range(100+1)]
        data = []
        for _ in range(n):
            b, x, y = map(int, input().split(' '))
            data.append([b, x, y])

        for i in range(n):
            b1, x1, y1 = data[i]
            for j in range(n):
                b2, x2, y2 = data[j]
                if b1 == b2:
                    continue
                dist = sqrt((x1 - x2)**2 + (y1 - y2)**2)
                if dist <= 50.0:
                    G[b1][b2] = dist
                    G[b2][b1] = dist

        m = int(input())
        for _ in range(m):
            s, g = map(int, input().strip().split(' '))
            if s == g:
                print(s)
                continue
            if (not 1<= s <= 100) or (not 1<= g <= 100):
                print('NA')
                continue
            d, p = dijkstra(s, G)
            if d[g] == float('inf'):
                print('NA')
            else:
                path = [g]
                while p[g] != s:
                    path.append(p[g])
                    g = p[g]
                path.append(s)
                rev = path[::-1]
                print(' '.join(map(str, rev)))


def main2(args):
    while True:
        n = int(input())
        if n == 0:
            break

        for _ in range(n):
            input()

        m = int(input())
        for _ in range(m):
            s, g = map(int, input().strip().split(' '))
            print('NA')


if __name__ == '__main__':
    main(sys.argv[1:])

Python: # AOJ 0155 Spider Jin
# Python3 2018.6.23 bal4u
# 最短経路問題

MAXLEN = 50
MAX = 100
INF = 0x7ffffffffffffff
x = [0]*(MAX+2)
y = [0]*(MAX+2)
dist = [INF]*(MAX+2)
pre = [0]*(MAX+2)
	
import heapq
def dijkstra(V, to, start, goal):
	global dist
	dist = [INF]*V
	Q = []
	dist[start] = 0
	heapq.heappush(Q, (0, start))
	while Q:
		t, s = heapq.heappop(Q)
		if s == goal: break
		if dist[s] < t: continue
		for e, cost in to[s]:
			nt = t + cost
			if dist[e] > nt:
				dist[e] = nt
				heapq.heappush(Q, (nt, e))
				pre[e] = s
while 1:
	n = int(input())
	if n == 0: break
	for i in range(n):
		j, x_, y_ = map(int, input().split())
		x[j], y[j] = x_, y_
	n += 1
	to = [[] for i in range(n)]
	for i in range(1, n):
		for j in range(i+1, n):
			dx, dy = x[i]-x[j], y[i]-y[j]
			cost = (dx**2 + dy**2)**0.5
			if cost <= MAXLEN:
				to[i].append((j, cost))
				to[j].append((i, cost))
	m = int(input())
	for i in range(m):
		s, g = map(int, input().split())
		if s == g: print(s)
		else:
			dijkstra(n, to, s, g)
			if dist[g] == INF: print("NA")
			else:
				ans = []
				ans.append(g)
				while g != s:
					g = pre[g]
					ans.append(g)
				print(*ans[::-1])

Python: import sys
readline = sys.stdin.readline
write = sys.stdout.write

from heapq import heappush, heappop

def solve(s):
    if s in memo:
        return memo[s]
    que = [(0, s)]
    dist = [10**18]*N
    prev = [None]*N
    dist[0] = 0
    while que:
        c, v = heappop(que)
        if dist[v] < c:
            continue
        for d, w in G[v]:
            if c + d < dist[w]:
                dist[w] = c + d
                prev[w] = v
                heappush(que, (c+d, w))
    memo[s] = prev
    return prev


while 1:
    N = int(readline())
    if N == 0:
        break
    P = [None]*N
    X = [0]*N; Y = [0]*N
    for i in range(N):
        b, x, y = map(int, readline().split())
        P[b-1] = complex(x, y)
    G = [[] for i in range(N)]
    for i in range(N):
        pi = P[i]
        for j in range(i+1, N):
            d = abs(pi - P[j])
            if d <= 50:
                G[i].append((d, j))
                G[j].append((d, i))

    memo = {}
    M = int(readline())
    for i in range(M):
        s, g = map(int, readline().split()); s -= 1; g -= 1
        prev = solve(s)
        if prev[g] is None:
            write("NA\n")
            continue
        res = [str(g+1)]
        while s != g:
            g = prev[g]
            res.append(str(g+1))
        res.reverse()
        write(" ".join(res))
        write("\n")