#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

typedef vector<int> L;
typedef pair<int,int> P;

class Node
{
public:
	L to;
	vector<double> co;
};

class Trl
{
public:
	int p;
	double c;
	L ord;
	Trl(int p, double c, L ord) : p(p), c(c), ord(ord) {}

	bool operator<(const Trl& t) const {
		return c > t.c;
	}
};

Node node[1000];
L dic;
vector<P> p;

pair<double, L> dijkstra(int s, int d)
{
	bool v[1000] = {0};
	priority_queue<Trl> q;
	q.push(Trl(s, 0.0, L()));
	while (!q.empty())
	{
		Trl t=q.top(); q.pop();
		if (v[t.p]) continue;
		v[t.p] = true;
		t.ord.push_back(t.p);

		if (t.p == d) 
			return pair<double, L>(t.c, t.ord);

		for (int i=0; i<node[t.p].to.size(); i++)
		{
			int next = node[t.p].to[i];
			if (v[next]) continue;

			q.push(Trl(next, t.c+node[t.p].co[i], t.ord));
		}

	}
	return pair<double, L>(-1.0, L());
}

int twd(P p1, P p2)
{
	return (p1.first-p2.first)*(p1.first-p2.first) + (p1.second-p2.second)*(p1.second-p2.second);
}

int rdic(int n)
{
	return find(dic.begin(), dic.end(), n) - dic.begin();
}

int main()
{
	int n;
	while (cin >> n, n)
	{
		dic.clear(); p.clear();
		memset(node, 0, sizeof(node));
		for (int i=0; i<n; i++)
		{
			int b, x, y;
			cin >> b >> x >> y;
			dic.push_back(b);
			p.push_back(P(x, y));
		}

		for (int i=0; i<n; i++)
		for (int j=i+1; j<n; j++)
		{
			int dd = twd(p[i], p[j]);
			if (dd > 2500) continue;
			node[i].to.push_back(j);
			node[i].co.push_back(sqrt((double)dd));
			node[j].to.push_back(i);
			node[j].co.push_back(sqrt((double)dd));
		}

		int m;
		cin >> m;

		while (m--)
		{
			int s, g;
			cin >> s >> g;
			pair<double,L> res = dijkstra(rdic(s), rdic(g));
			
			if (res.second.empty())
			{
				cout << "NA" << endl;
			}
			else
			{
				int s = res.second.size()-1;
				for (int i=0; i<s; i++)
					cout << dic[res.second[i]] << ' ';
				cout << dic[res.second[s]] << endl;
			}
		}
	}
	return 0;
}