Village

After countless days and nights of exploration by scientists, in the year 6101 AD, humanity finally discovered a habitable planet outside of Earth, planet W. This planet has a natural environment almost identical to that of Earth.

As countless Earthlings vied to immigrate to planet W, Dongdong, the secretary of the Human Alien Immigration Planning Department, suggested to the Minister that immigration should be carried out in planned batches rather than all at once. The Minister accepted Dongdong's suggestion and decided to first immigrate $n$ people to the most suitable plain on planet W to form a new village. After careful surveying, the Human Alien Immigration Planning Department selected a $1v \times 1v$ square plain area on planet W (where $v$ is a unit of length). Everyone's residence must be within this area (they may be on the boundary). To describe the position of a point within the area, people established a two-dimensional coordinate system with one vertex of the area as the origin and its adjacent sides as the positive directions, as shown in the figure below:

To ensure the harmonious and rapid development of this new village, the Minister ordered Dongdong to plan the village: determine their residential locations based on the relationships among the $n$ immigrants. For any two people among the immigrants, there are two types of relationships: they either know each other or they do not. Through long-term research, Dongdong found a condition that allows the village to develop best: the distance between people who do not know each other should be as large as possible, while the distance between people who know each other should be neither too large nor too small.

To quantify these two conditions, Dongdong defined several concepts:

Stranger Distance: The average distance between all pairs of people who do not know each other, expressed by formula (1):

$$\bar{d} = \frac{1}{C_1} \sum_{i,j \text{ not acquainted}} D_{i,j} \quad (1)$$

where $C_1$ is the number of pairs of people who do not know each other, and $D_{i,j}$ represents the distance between $i$ and $j$. If the coordinates of $i$ are $(x_i, y_i)$ and the coordinates of $j$ are $(x_j, y_j)$, then:

$$D_{i,j} = \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2} \quad (2)$$

Friendly Distance: The average distance between all pairs of people who know each other, expressed by formula (3):

$$\bar{a} = \frac{1}{C_2} \sum_{i,j \text{ acquainted}} D_{i,j} \quad (3)$$

where $C_2$ is the number of pairs of people who know each other.

Friendly Variation Coefficient $v$: The standard deviation of the distances between people who know each other, expressed by formula (4):

$$v = \sqrt{\frac{1}{C_2} \sum_{i,j \text{ acquainted}} (D_{i,j} - \bar{a})^2} \quad (4)$$

Dongdong proposed a planning goal:

Make $(1.5 - v)^4 \bar{d}$ as large as possible!

Task

This is an answer-submission problem.

There are 10 input files in the problem directory, village1.in ~ village10.in, describing the $n$ people to be immigrated. You need to generate the corresponding village1.out ~ village10.out to tell Dongdong where these $n$ people should be moved to on the plain.

Input

Read data from village1.in ~ village10.in. The first line of the data is an integer $n$, representing how many people the Minister is preparing to immigrate to planet W.

The next line is an integer $m$, representing how many pairs of people among these $n$ people know each other.

The next $m$ lines each contain two integers $a, b$, representing that $a$ and $b$ know each other.

The input data guarantees that each pair of people who know each other is described only once. That is, if $a, b$ appears, $b, a$ or $a, b$ will not appear again.

Output

Output to village1.out ~ village10.out. The output should contain $n$ lines, each with two real numbers. The two real numbers $x_i$ and $y_i$ in the $i$-th line represent the coordinates of the $i$-th person's residence. You may keep as many significant digits as you need, but you cannot use scientific notation.

Examples

Input 1

4
4
1 2
2 3
3 4
4 1

Output 1

0 0
0 1.0
1 1.000
0.00000 0.0

Scoring

For each test case, we have a preset expectation $e$. If your solution is valid (i.e., everyone is within the plain), your score is:

$$\left\lfloor \min\left\{\max\left\{\frac{(1.5 - v)^4 \bar{d} - 0.5e}{0.5e}, 0\right\}, 1\right\} \times \text{test case points} \right\rfloor$$

where $\min\{a, b\}$ represents the smaller of $a$ and $b$, $\max\{a, b\}$ represents the larger of $a$ and $b$, and $\lfloor x \rfloor$ represents the largest integer not greater than $x$. $v$ and $\bar{d}$ are as defined above.

If your solution is invalid, the score for this test case is 0.

Note

In the solution you provide, more than one person may reside at the same location.