#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
struct grid {ll to; ld cost;};
using Graph = vector<vector<grid>>;
using P = pair<ld, ll>;
constexpr ll INF = 1ll<<60;	   
ld distance(ll x1, ll y1, ll x2, ll y2)
{
	return sqrt(pow(x1-x2, 2)+pow(y1-y2, 2));
}

int main(int argc, char **argv)
{
	while (true)
	{
		ll N; cin >> N;
		if (N == 0)break;
		vector<pair<ll, ll>> coo(N);
		vector<ll> id(N);
		for (ll i = 0; i < N; ++i)
		{
			ll x, y; cin >> id[i] >> x >> y;
			coo[i] = P(x, y);
			--id[i];
		}
		
		Graph G(N);
		for (ll i = 0; i < N; ++i)
		{
			for (ll j = 0; j < N; ++j)
			{
				if (id[i] == id[j]) continue;
				ld d = distance(coo[i].first, coo[i].second, coo[j].first, coo[j].second);
				if (d <= 50.0)
				{
					G[id[i]].push_back(grid{id[j], d});
				}
			}
		}

		ll m; cin >> m;
		for (ll _ = 0; _ < m; ++_)
		{
			ll s, g; cin >> s >> g;
			--s, --g;
			priority_queue<P, vector<P>, greater<P>> que;
			que.push(P(0.0, s));
			vector<ld> dist(N, INF);
			dist[s] = 0.0;
			vector<ll> his(5010, -1);
			vector<ll> ans;
			
			while (!que.empty())
			{
				P p = que.top(); que.pop();
				ll now = p.second;
				if (dist[now] < p.first) continue;

				if (now == g)
				{
					ans.push_back(g);
					ll tmp = g;
					while (tmp != s)
					{
						tmp = his[tmp];
						ans.push_back(tmp);
					}
					break;
				}

				for (auto &nv : G[now])
				{
					ld nc = dist[now] + nv.cost;
					if (dist[nv.to] > nc)
					{
						dist[nv.to] = nc;
						que.push(P(dist[nv.to], nv.to));
						his[nv.to] = now;
					}
				}
			}

			// output
			if (ans.empty())
				std::cout << "NA" << std::endl;
			else
			{
				for (ll i = 0; i < ans.size(); ++i)
					std::cout << (i ? " " : "") << ans[ans.size()-1-i]+1;
				std::cout << std::endl;
			}
		}
			
	}
}

