1. 


/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS09
* Problem: 10147 - Highways
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1088
*
* @author Dennis Wilfert
* @version 1.0, 10/28/2009
*
* Method : MST (Kruskal)
* Status : Accepted
* Runtime: 2.040
*/
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

class Main {

public static void main(String[] args) throws IOException {

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
PrintWriter writer = new PrintWriter(new BufferedOutputStream(System.out));

StringTokenizer token;
// Anzahl der Testfälle
int cases = Integer.parseInt(reader.readLine());
int[][] towns;
boolean[][] streets;
int townnum, streetnum;
int[][] coordinates;
int temp;
boolean highway;

while (cases > 0) {

reader.readLine();

// Anzahl der Städte
townnum = Integer.parseInt(reader.readLine());
// Koordinaten der Städte
towns = new int[townnum][3];
for (int i = 0; i < townnum; i++) {
token = new StringTokenizer(reader.readLine());

towns[i][0] = Integer.parseInt(token.nextToken());
towns[i][1] = Integer.parseInt(token.nextToken());
towns[i][2] = i;
}

// Anzahl der bereits gebauten Highways
streetnum = Integer.parseInt(reader.readLine());
// Boolean-Array zum eintragen der bereits gebauten Highways
streets = new boolean[townnum][townnum];

for (int i = 0; i < streetnum; i++) {
token = new StringTokenizer(reader.readLine());
int a = Integer.parseInt(token.nextToken()) - 1;
int b = Integer.parseInt(token.nextToken()) - 1;

streets[a][b] = true;
streets[b][a] = true;
}

// Verbindungslänge zwischen den verschiedenen Städten berechnen
coordinates = new int[townnum > 2 ? (townnum * townnum - 1) / 2 : 2][3];
int k = 0;
for (int i = 0; i < townnum; i++) {
for (int j = i + 1; j < townnum; j++) {
coordinates[k][0] = i;
coordinates[k][1] = j;
// Längen nur berechnen wenn nicht bereits ein Highway existiert
if (!streets[i][j]) {
coordinates[k][2] = (towns[i][0] - towns[j][0]) * (towns[i][0] - towns[j][0]) + (towns[i][1] - towns[j][1]) * (towns[i][1] - towns[j][1]);
}
k++;
}
}

// Nach längen sortieren
if (k > 1) {
sort(coordinates, 0, k - 1);
}

highway = false;

///////////////// Kruskal Algorithmus zum berechnen der Kürzesten Verbindung ////////////////
// Array mit den Abständen durchlaufen
for (int i = 0; i < coordinates.length; i++) {
// Sind die Werte an den beiden Positionen unterschiedlich wird
// der erste Wert gesucht und durch den zweiten ersetzt sowie der Abstand zur Summe addiert,
// bis nur noch immer der selbe Wert in coordinates[][2] steht, dann wurde
// der kürzeste Weg gefunden.
if (towns[(int) coordinates[i][0]][2] != towns[(int) coordinates[i][1]][2]) {
temp = towns[(int) coordinates[i][0]][2];
// Array mit den Koordinaten durchlaufen
for (int j = 0; j < towns.length; j++) {
if (towns[j][2] == temp) {
towns[j][2] = towns[(int) coordinates[i][1]][2];
}
}
// Wert dazuaddieren
if (coordinates[i][2] != 0) {
writer.println((coordinates[i][0] + 1) + " " + (coordinates[i][1] + 1));
highway = true;
}
}

}
/////////////////////////////////////////////////////////////////////
if (!highway) {
writer.println("No new highways need");
}


cases--;
if (cases > 0) {
writer.println();
}
}
writer.flush();
}

public static void sort(int[][] a, int start, int end) {
int[] tmp;
int i = start;
int j = end;
int x = a[(start + end) / 2][2];

do {
// Vom Startpunkt aus einen Wert suchen der >= x ist
while (a[i][2] < x) {
i++;
}
// Vom Endpunkt aus einen Wert suchen der <= x ist
while (a[j][2] > x) {
j--;
}

// a[i] und a[j] tauschen
if (i <= j) {
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
i++;
j--;
}
} while (i <= j);

if (start < j) {
sort(a, start, j);
}

if (i < end) {
sort(a, i, end);
}
}
}


2.


/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS09
* Problem: 10147 - Highways
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1088
*
* @author Dennis Wilfert
* @version 1.0, 10/28/2009
*
* Method : MST (Prim)
* Status : Accepted
* Runtime: 1.868
*/
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

class Main {

public static void main(String[] args) throws IOException {

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
PrintWriter writer = new PrintWriter(new BufferedOutputStream(System.out));

StringTokenizer token;
// Anzahl der Testfälle
int cases = Integer.parseInt(reader.readLine());
int[][] towns;
boolean[][] streets;
int townnum, streetnum;
int[][] coordinates;
boolean[] nodes;
int head;
boolean highway;

while (cases > 0) {

reader.readLine();

// Anzahl der Städte
townnum = Integer.parseInt(reader.readLine());
// Koordinaten der Städte
towns = new int[townnum][2];
for (int i = 0; i < townnum; i++) {
token = new StringTokenizer(reader.readLine());

towns[i][0] = Integer.parseInt(token.nextToken());
towns[i][1] = Integer.parseInt(token.nextToken());
}

// Anzahl der bereits gebauten Highways
streetnum = Integer.parseInt(reader.readLine());
// Boolean-Array zum eintragen der bereits gebauten Highways
streets = new boolean[townnum][townnum];

for (int i = 0; i < streetnum; i++) {
token = new StringTokenizer(reader.readLine());
int a = Integer.parseInt(token.nextToken()) - 1;
int b = Integer.parseInt(token.nextToken()) - 1;

streets[a][b] = true;
streets[b][a] = true;
}

// Verbindungslänge zwischen den verschiedenen Städten berechnen
coordinates = new int[townnum > 2 ? (townnum * townnum - 1) / 2 : 2][5];
int k = 0;
for (int i = 0; i < townnum; i++) {
for (int j = i + 1; j < townnum; j++) {
coordinates[k][0] = i;
coordinates[k][1] = j;
// Längen nur berechnen wenn nicht bereits ein Highway existiert
if (!streets[i][j]) {
coordinates[k][2] = (towns[i][0] - towns[j][0]) * (towns[i][0] - towns[j][0]) + (towns[i][1] - towns[j][1]) * (towns[i][1] - towns[j][1]);
}
k++;
}
}

// Nach längen sortieren
if (k > 1) {
sort(coordinates, 0, k - 1);
}

// Jeweils die vorherigen und die nächste Position zu jedem Wert eintragen
for (int i = 0; i < k; i++) {
coordinates[i][3] = i - 1;
coordinates[i][4] = i + 1;
}


highway = false;

///////////////// Prim Algorithmus zum berechnen der Kürzesten Verbindung ////////////////
nodes = new boolean[townnum];
head = 0;
nodes[0] = true;
int i;
// Alle Knoten durchlaufen
for (int j = townnum - 1; j > 0; j--) {
i = head;
while (i < k) {
// Steht weder der Anfangs- noch der Endknoten der Straße auf true wird mit dem nächsten Wert weitergemacht
if (!nodes[coordinates[i][0]] && !nodes[coordinates[i][1]]) {
i = coordinates[i][4];
} // Steht mindestens einer der Beiden Knoten der aktuellen Straße auf true
else {
// Ist der Vorgängerwert -1, bekommt die nachfolgende Straße auch -1 als Vorgängerwert
if (coordinates[i][3] == -1) {
coordinates[coordinates[i][4]][3] = coordinates[i][3];
} // Ansonsten bekommt die vorherige Straße den nachfolgerwert als nächste Straße
// und doie nachfolgende Straße die Vorgängerstraße als vorherige Straße
else {
coordinates[coordinates[i][3]][4] = coordinates[i][4];
coordinates[coordinates[i][4]][3] = coordinates[i][3];
}
// Ist nur einer der beiden Knotenpunke der Straße auf true wird der andere Knotenpunkt auch auf true gesetzt und die Länge
// der Straße von der Gesamtlänge des Straßennetzes abgezogen, d.h. die Straße kann ohne Beleuchtung auskommen.
if ((nodes[coordinates[i][0]] && !nodes[coordinates[i][1]]) || (nodes[coordinates[i][1]] && !nodes[coordinates[i][0]])) {
nodes[nodes[coordinates[i][0]] ? coordinates[i][1] : coordinates[i][0]] = true;
if (coordinates[i][2] != 0) {
writer.println((coordinates[i][0] + 1) + " " + (coordinates[i][1] + 1));
highway = true;
}
// Ist der Vorgängerwert -1 wird der Nachfolgerwert als Startpunkt für die while-Schleife gesetzt, ansonsten wird mit
// dem alten Startwert begonnen
if (coordinates[i][3] == -1) {
head = coordinates[i][4];
}
// Schleife unterbrechen
break;
}
i = coordinates[i][4];
}
}
}
/////////////////////////////////////////////////////////////////////
if (!highway) {
writer.println("No new highways need");
}


cases--;
if (cases > 0) {
writer.println();
}
}
writer.flush();
}

public static void sort(int[][] a, int start, int end) {
int[] tmp;
int i = start;
int j = end;
int x = a[(start + end) / 2][2];

do {
// Vom Startpunkt aus einen Wert suchen der >= x ist
while (a[i][2] < x) {
i++;
}
// Vom Endpunkt aus einen Wert suchen der <= x ist
while (a[j][2] > x) {
j--;
}

// a[i] und a[j] tauschen
if (i <= j) {
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
i++;
j--;
}
} while (i <= j);

if (start < j) {
sort(a, start, j);
}

if (i < end) {
sort(a, i, end);
}
}
}