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 Junior Championship March'2005

About     Problems     Submit solution     Judge status     Standings
Contest is over

L. Cables

Time limit: 0.25 second
Memory limit: 64 MB
There are N computers in a computer club. It’s known which computers are to be connected with a cable in order to make the net work properly. It’s left to arrange the computers so that no two cables intersect and distance between every two computer would be greater than one. Regard the computers as points and the cables as line segments. The net is connected, i.e. every two computers are connected with some sequence of cables.

Input

First line contains integer N (1 ≤ N ≤ 1000). Then N−1 lines follow. In each line there are two integers ai and bi, the numbers of computers that are to be connected with a cable (1 ≤ ai, bi ≤ N).

Output

You should output N lines. In the ith line there should be two real numbers — coordinates of the ith computer. The absolute values of the coordinates shouldn’t exceed 1000.

Sample

inputoutput
3
1 2
2 3
0 0
10 0
0 10
Problem Author: Den Raskovalov (text by Aleksandr Bikbaev)
Problem Source: USU Junior Championship March'2005
To submit the solution for this problem go to the Problem set: 1358. Cables