#include<cstdio>
#include<vector>
#include<queue>
#include<utility>
#include<climits>
#include<functional>
#include<algorithm>
using namespace std;

const int N = 1001;
const int MAX_DISTANCE = 50*50;
double dis2[N][N];
template<class T>
inline T Square(T x){return (x*x);}


vector<int> F(int n, int from, int to)
{
	int i;
	pair<double, vector<int> > bill[N];
	for(i = 0; i <= n; ++i) bill[i].first = INT_MAX;

	typedef pair<double,int> PDI;
	priority_queue<PDI, vector<PDI>, greater<PDI> > q;	PDI p;

	q.push(make_pair(0, from));
	bill[from].first = 0;
	bill[from].second.push_back(from);
	while(!q.empty())
	{
		p = q.top(), q.pop();

		for(i = 1; i <= n; ++i)
		{
			if(dis2[p.second][i] <= MAX_DISTANCE &&
				bill[i].first > bill[p.second].first + dis2[p.second][i])
			{
				bill[i].first = bill[p.second].first + dis2[p.second][i];
				bill[i].second = bill[p.second].second;
				bill[i].second.push_back(i);
				q.push(make_pair(bill[i].first, i));
			}
		}
	}
	return bill[to].second;
}

int main()
{
	int n,m,i,j,b,x,y,from,to;
	pair<int,int> pos[N];	//<x, y>

	while(scanf("%d",&n),n)
	{
		for(i = 1; i <= n; ++i)
		{
			scanf("%d%d%d",&b,&x,&y);
			pos[b].first = x, pos[b].second = y;
		}
		for(i = 1; i <= n; ++i)
		{
			for(j = 1; j <= n; ++j)
			{
				if(i==j) dis2[i][j] = dis2[j][i] = MAX_DISTANCE*5;
				else
				{
					dis2[i][j] = Square(pos[i].first-pos[j].first) + Square(pos[i].second-pos[j].second);
					dis2[j][i] = dis2[i][j];
				}
			}
		}
		scanf("%d",&m);
		for(i=0;i<m;++i)
		{
			scanf("%d%d",&from,&to);
			vector<int>v = F(n,from,to);
			if( v.empty())
				puts("NA");
			else
			{
				for(vector<int>::iterator ite = v.begin(); ite != v.end(); ++ite)
				{
					printf("%s%d", (ite!=v.begin()?" ":""), *ite);
				}
				putchar('\n');
			}
		}
	}
	return 0;
}