#include <iostream>
#include <math.h>
#include <string.h>
#include <queue>
using namespace std;

struct Building
{
	int index;
	int x;
	int y;

	double distanceTo(const Building& obj)
	{
		return sqrt((x-obj.x)*(x-obj.x) + (y-obj.y)*(y-obj.y));
	}
};

struct Path
{
	int connectingIndex;
	double distance;
};

struct Agent
{
	int index;
	int prev_index;
	double distance;

	bool operator<(const Agent& rhs) const
	{
		return distance > rhs.distance;
	}
};

int n, m;
Building buildings[100];
vector<vector<Path>> edges;
int prev_index[100];
priority_queue<Agent> que;
bool defined[100];

int main()
{
	while (true)
	{
		cin >> n;
		if (n == 0)
		{
			return 0;
		}

		// initialize
		edges.assign(n, vector<Path>());

		// input
		for (int i = 0; i < n; ++i)
		{
			cin >> buildings[i].index
				>> buildings[i].x
				>> buildings[i].y;
		}

		// calc distance
		for (int i = 0; i < n; ++i)
		{
			for (int j = i + 1; j < n; ++j)
			{
				Building A = buildings[i];
				Building B = buildings[j];
				double distance = A.distanceTo(B);
				if (distance <= 50.0)
				{
					int indexA = A.index - 1;
					int indexB = B.index - 1;
					edges[indexA].push_back(Path{ indexB, distance });
					edges[indexB].push_back(Path{ indexA, distance });
				}
			}
		}
		
		// query loop
		cin >> m;
		for (int i = 0; i < m; ++i)
		{
			int s, g;
			cin >> s >> g;

			// initialize
			que = priority_queue<Agent>();
			memset(defined, 0, sizeof defined);

			// dijkstra
			bool found_goal = false;
			que.push(Agent{ s - 1, 0 });
			while (!que.empty())
			{
				Agent agent = que.top(); que.pop();
				
				if (defined[agent.index])
				{
					continue;
				}
				defined[agent.index] = true;
				prev_index[agent.index] = agent.prev_index;

				if (agent.index == g - 1)
				{
					found_goal = true;
					break;
				}

				for (auto path : edges[agent.index])
				{
					if (!defined[path.connectingIndex])
					{
						que.push(Agent{ path.connectingIndex,
						                agent.index,
						                agent.distance + path.distance });
					}
				}
			}

			// output
			if (!found_goal)
			{
				cout << "NA" << endl;
			}
			else
			{
				vector<int> path;
				int agent = g - 1;
				while (agent != s - 1)
				{
					path.push_back(agent + 1);
					agent = prev_index[agent];
				}
				cout << s;
				for (auto itr = path.rbegin(); itr != path.rend(); ++itr)
				{
					cout << ' ' << *itr;
				}
				cout << endl;
			}
		} // end of query loop
	} // end of while
}