#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <iostream>
#include <sstream>
#include <climits>
#include <cfloat>
#include <complex>


typedef long long ll;
const double Eps = 1e-4;

using namespace std;

typedef pair<int, double> P;
double dis(int x, int y)
{
	return sqrt((double)x*x+y*y);
}
int main()
{
	int n;
	while (scanf("%d", &n), n)
	{
		int no[1000];
		int x[1001], y[1001];
		for (int i = 0; i < n; ++i)
		{
			int a, b, c;
			scanf("%d %d %d", &a, &b, &c);
			no[i] = a;
			x[a] = b;
			y[a] = c;
		}
		vector<P> reach[1001];
		for (int i = 0; i < n; ++i)
		{
			for (int j = i+1; j < n; ++j)
			{
				double t = dis(x[no[i]]-x[no[j]], y[no[i]]-y[no[j]]);
				if (t < 50 + Eps)
				{
					reach[no[i]].push_back(P(no[j], t));
					reach[no[j]].push_back(P(no[i], t));
				}
			}
		}
		
		int m;
		scanf("%d", &m);
		while (m--)
		{
			int from[1001];
			double d[1001];
			const int Inf = 100000000;
			for (int i = 0; i < 1001; ++i)
				d[i] = from[i] = Inf;
			int s, g;
			scanf("%d %d", &s, &g);
			priority_queue<P, vector<P>, greater<P> > nodes;
			nodes.push(P(0, s));
			d[s] = 0;
			from[s] = -1;
			while (!nodes.empty())
			{
				P v = nodes.top();
				nodes.pop();
				int id = v.second;
				if (id == g)
					break;
				else if (v.first > d[id])
					continue;

				for (int i = 0; i < reach[id].size(); ++i)
				{
					int to = reach[id][i].first;
					double cost = reach[id][i].second;
					if (v.first + cost < d[to])
					{
						d[to] = v.first + cost;
						from[to] = id;
						nodes.push(P(d[to], to));
					}
				}
			}
			if (d[g] != Inf)
			{
				vector<int> path;
				for (int i = g; i != -1; i = from[i])
					path.push_back(i);
				for (int i = path.size() - 1; i > 0; --i)
					printf("%d ", path[i]);
				printf("%d\n", path[0]);
			}
			else
				puts("NA");
		}
	}

	return 0;
}