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.

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

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