ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

USU Personal Contest 2002

About     Problems     Submit solution     Judge status     Standings
Contest is over

D. Akbardin’s Roads

Time limit: 1.0 second
Memory limit: 64 MB
Great Akbardin decided to build new roads in his caliphate. He wants to build minimal number of roads so that one can travel from any town to any other using only these roads. But this problem is too difficult for him and his mathematicians. So, at first, they decided to build straight roads between towns in such a way, that every town becomes connected with only one other. Because crossroads make movement dangerous, no two roads should intersect.
You task is to make plan of the roads being given coordinates of towns.

Input

First line contains an even integer N (N ≤ 10000) — the number of towns. Each of the next N lines contains pair of integers — coordinates of i-th town xi, yi (−109 < xi, yi < 109). No three towns lay on one line.

Output

Output N/2 lines with description of one road on each. Road is identified by pair of towns it connects. If there are several correct answers, output any of them.

Sample

inputoutput
4
0 2
1 1
3 4
4 4
1 3
2 4
Problem Author: Pavel Atnashev
Problem Source: Third USU personal programming contest, Ekaterinburg, Russia, February 16, 2002
To submit the solution for this problem go to the Problem set: 1178. Akbardin’s Roads