#include<iostream>
#include<cstring>
#include<set>
#include<cmath>

double adjacive[1000][1000];
int field[1000][1000];
int prev[1000];
std::set<int> building;

int input();
void dijkstra(int start);
void output(int start,int goal);

int main()
{
	while(1)
	{
		int n;
		n=input();
		if(n==0)break;
		
		int m;
		std::cin>>m;
		for(int i=0;i<m;i++)
		{
			int bs,bg;
			std::cin>>bs>>bg;
			dijkstra(bs);
			output(bs,bg);
		}
	}
	return 0;
}

int input()
{
	int n;
	std::cin>>n;
	if(n==0)return 0;
	memset(field,0,sizeof(field));
	building.clear();

	for(int i=0;i<1000;i++){for(int j=0;j<1000;j++){adjacive[i][j]=1.0e+10;}}

	for(int i=0;i<n;i++)
	{
		int b,x,y;
		std::cin>>b>>x>>y;
		field[y][x]=b;
		building.insert(b);
	}
	for(int y=0;y<1000;y++)
	{
		for(int x=0;x<1000;x++)
		{
			if(field[y][x]!=0)
			{
				for(int i=-50;i<=50;i++)
				{
					for(int j=-50;j<=50;j++)
					{
						if(i+y>=0&&i+y<1000&&j+x>=0&&j+x<1000&&field[i+y][j+x]!=0&&i*i+j*j<=2500)//genarate adjacive matrix
						{
							adjacive[field[y][x]-1][field[y+i][x+j]-1]=hypot(i,j);
						}
					}
				}
			}
		}
	}
	return n;
}

void dijkstra(int start)
{
	bool visited[1000];
	double cost[1000];
	memset(visited,0,sizeof(visited));
	memset(prev,-1,sizeof(prev));

	for(int i=0;i<1000;i++){cost[i]=1.0e+10;}
	
	cost[start-1]=0;
	while(1)
	{
		int u=-1;
		for(std::set<int>::iterator it=building.begin();it!=building.end();it++)
		{
			if(!visited[*it-1]&&(u==-1||cost[*it-1]<cost[u]))
			{
				u=*it-1;
			}
		}
		if(u==-1)break;
		visited[u]=true;
		for(std::set<int>::iterator it=building.begin();it!=building.end();it++)
		{
			if(cost[*it-1]>cost[u]+adjacive[u][*it-1])
			{
				cost[*it-1]=cost[u]+adjacive[u][*it-1];
				prev[*it-1]=u;
				
			}
		}
	}
}

void output(int start,int goal)
{
	int temp[1000];
	int b=goal-1;
	int i=0;
	bool isNA=true;

	while(prev[b]!=-1)
	{
		temp[i]=b+1;
		i++;
		b=prev[b];
		isNA=false;
	}

	if(isNA)
	{
		std::cout<<"NA"<<std::endl;
	}
	else
	{
		std::cout<<start;
		for(i=i-1;i>=0;i--)
		{
			std::cout<<' '<<temp[i];
		}
		std::cout<<std::endl;
	}
}