Zadanie 1178 (Droga Akbardina)

Treść

Wielki Akbardin postanowił zbudować nowe drogi w swoim kalifacie. Chce zbudować możliwie najmniejszą liczbę dróg tak, aby dało się dojechać z każdego miasta do dowolnego innego używając tylko tych dróg. Niestety ten probral jest zbyt trudny dla niego oraz jego matematyków. Na początku postanowił więc zbudować proste drogi pomiędzy miastami w taki sposób, aby każde miasto było połączone z jakimś innym. Niestety skrzyżowania mogą tworzyć zagrożenia, więc żadne dwie drogi nie powinny się przecinać.
Twoim zadaniem jest stworzyć plan sieci dróg znając współrzędne miast.

Specyfikacja wejścia

Pierwsza linia zawiera zawiera jedną liczbę parzystą N (N ≤ 10000) - liczbę miast. Każda z kolejnych N linii zawiera parę liczb całkowitych - współrzędnych i-tego miasta x_i, y_i (-10^9 < x_i, y_i < 10^9). Żadne trzy miasta nie leżą na jednej linii.

Specyfikacja wyjścia

Na wyjściu należy wypisać N/2 linii opisujących drogi. Droga jest wyznaczona przez parę miast, które łączy (w linii prostej).

Przykład

Wejście

4
0 2
1 1
3 4
4 4

Wyjście

1 3
2 4