/*
 * main.cpp
 *
 *  Created on: Sep 18, 2008
 *      Author: Chris
 */

#include <cstdio>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;

struct town {
	int id;
};

town towns[750];
int groups[750];
int xval[750];
int yval[750];
int closest[750];
long dist[750];

struct road {
	int a;
	int b;
	long dist;
	road(int i, int j) : a(i), b(j), dist((xval[i] - xval[j]) * (xval[i] - xval[j])
			+ (yval[i] - yval[j]) * (yval[i] - yval[j])) {}
};

bool compare(const town& a, const town& b) { return groups[a.id] < groups[b.id]; }
bool compare2(const town& a, const town& b) { return dist[a.id] < dist[b.id]; }

map<int, vector<int> > roads;

int num_cases, num_towns, num_roads;

void mark(int id) {
	vector<int>& away = roads[id];
	for (int i = 0; i < away.size(); i++) {
		if (groups[away[i]] == 0) continue;
		groups[away[i]] = 0;
		mark(away[i]);
	}
}

void update(int curr, int next) {
	for (int i = curr; i < next; i++) {
		int a = towns[i].id;
		for (int j = next; j < num_towns; j++) {
			int b = towns[j].id;
			road r(a, b);
			if (r.dist < dist[b]) {
				dist[b] = r.dist;
				closest[b] = a;
			}
		}
	}
}

int main() {
	scanf("%d", &num_cases);

	for (int case_n = 0; case_n < num_cases; case_n++) {
		if (case_n != 0) printf("\n");
		scanf("%d", &num_towns);
		for (int i = 0; i < num_towns; i++) {
			int x, y;
			scanf("%d %d", &x, &y);
			groups[i] = i;
			xval[i] = x;
			yval[i] = y;
			towns[i].id = i;
			dist[i] = 20000 * 20000;
		}

		scanf("%d", &num_roads);

		roads.clear();
		for (int i = 0; i < num_roads; i++) {
			int a, b;
			scanf("%d %d", &a, &b);
			roads[--a].push_back(--b);
			roads[b].push_back(a);
		}

		int curr = 0;
		int num_built = 0;
		while (true) {
			mark(towns[curr].id);

			sort(towns + curr, towns + num_towns, &compare);

			int next = 0;
			while (next < num_towns && groups[towns[next].id] == 0) next++;
			if (next == num_towns) break;

			update(curr, next);
			sort(towns + next, towns + num_towns, &compare2);

			printf("%d %d\n", towns[next].id + 1, closest[towns[next].id] + 1);

			groups[towns[next].id] = 0;
			curr = next;
			num_built++;
		}

		if (num_built == 0) printf("No new highways needed.\n");
	}
	return 0;
}

