Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0155

"""
import sys
from sys import stdin
from math import sqrt
from heapq import heappush, heappop
input = stdin.readline


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

    d[s] = 0
    while True:
        mincost = float('inf')
        # ??\??????????????§??????????????¨?????????????????????u???????????????
        for i in range(node):
            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(node):
            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')] * (n+1) for _ in range(n+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
                d = sqrt((x1 - x2)**2 + (y1 - y2)**2)
                if d <= 50.0:
                    G[b1][b2] = d
                    G[b2][b1] = d

        m = int(input())
        for _ in range(m):
            s, g = map(int, input().split(' '))
            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)))


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

Fixed submission:
# -*- 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().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):
            b, x, y = map(int, input().split())

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


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

Buggy python submission (verdict: Runtime Error):
# -*- 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
    node = len(G)
    d = [float('inf')] * 101
    color = [WHITE] * 101
    p = [-1] * 101

    d[s] = 0
    while True:
        mincost = float('inf')
        # ??\??????????????§??????????????¨?????????????????????u???????????????
        for i in range(node):
            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(node):
            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
                d = sqrt((x1 - x2)**2 + (y1 - y2)**2)
                if d <= 50.0:
                    G[b1][b2] = d
                    G[b2][b1] = d

        m = int(input())
        for _ in range(m):
            s, g = map(int, input().split(' '))
            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)))


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

Fixed submission:
# -*- 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().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):
            b, x, y = map(int, input().split())

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


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

Buggy python submission (verdict: Runtime Error):
# -*- 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
                d = sqrt((x1 - x2)**2 + (y1 - y2)**2)
                if d <= 50.0:
                    G[b1][b2] = d
                    G[b2][b1] = d

        m = int(input())
        for _ in range(m):
            s, g = map(int, input().split(' '))
            if s == g:
                print(s)
                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)))


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

Fixed submission:
# -*- 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().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):
            b, x, y = map(int, input().split())

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


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

Buggy python submission (verdict: Runtime Error):
# -*- 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
                d = sqrt((x1 - x2)**2 + (y1 - y2)**2)
                if d <= 50.0:
                    G[b1][b2] = d
                    G[b2][b1] = d

        m = int(input())
        for _ in range(m):
            s, g = map(int, input().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)))


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

Fixed submission:
# -*- 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().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):
            b, x, y = map(int, input().split())

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


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

Buggy python submission (verdict: Runtime Error):
# -*- 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
                d = sqrt((x1 - x2)**2 + (y1 - y2)**2)
                if d <= 50.0:
                    G[b1][b2] = d
                    G[b2][b1] = d

        m = int(input())
        for _ in range(m):
            s, g = map(int, input().split(' '))
            print('NA')
            continue
            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)))


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

Fixed submission:
# -*- 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().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):
            b, x, y = map(int, input().split())

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


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

Buggy python submission (verdict: Runtime Error):
# -*- 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().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):
            b, x, y = map(int, input().split(' '))

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


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

Fixed submission:
# -*- 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().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):
            b, x, y = map(int, input().split())

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


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

Buggy python submission (verdict: Runtime Error):
# -*- 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().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().split(' '))
            print('NA')


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

Fixed submission:
# -*- 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().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):
            b, x, y = map(int, input().split())

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


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

Buggy python submission (verdict: Runtime Error):
# -*- 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:])

Fixed submission:
# -*- 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().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):
            b, x, y = map(int, input().split())

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


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

Buggy python submission (verdict: Runtime Error):
# -*- 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):
            b, x, y = map(int, input().split(' '))

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


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

Fixed submission:
# -*- 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().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):
            b, x, y = map(int, input().split())

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


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