31379번 - Mosaic Tracery 스페셜 저지다국어

문제

One of the squares of the town in far-away Oriental country is art mosaic panel consisting of multicolored tiles. The most attractive square feature for tourists is that sometimes some set of tiles is extracted from the mosaic panel and replaced by tiles of another color, thus the mosaic tracery has changed.

Square surface is modelled by the peace of square plane and every tile is the square with side of length one on the plane. Mosaic piece that is planned to output is defined by following algorithm. At the first is marked any tile, then any another that have common side with the first, then any from residual tiles that have common side with one of the already taken tiles and so on. Becouse the painter entrusted with new picture drawing lives in other town the tile desription had been writed before outputting them. All points of square grid that are the corners of at least one of the extracting multicolored tiles were numbered from 1ドル$ to $N$. After that the sequence of all pairs of neighbour points, that is either their $x$-coordinates are equal and the absolute value of difference of $y$-coordinates is one or their $y$-coordinates are equal and the absolute value of difference of $x$-coordinates is one, had been writed.

However before that description have been got to the painter it was been fallen into hands of mathematicians. As a result of their interest for various graph transformations the points turned out renumbered in chaotic order although their numbers are still different numbers from 1ドル$ to $N$ and pair of points in sequence are neighbours.

Thus is needed program for painter that reconstructs from this description initial coordinates of mosaic corners. With all this going on may be multiple variants but program may output any of possible variants becouse rotation or reflection is not a problem for painter.

입력

The first line of input contains two integers $N$ and $M$: the number of numbered points and the number of pairs of neighbour points (4ドル \le N \le 100,000円$). Each of next following lines contains two integers $U_{i}$ and $V_{i}$: numbers of neighbour points (1ドル \le U_{i}, V_{i} \le N,ドル 1ドル \le i \le M$). It is guaranteed that answer exists.

출력

Output $N$ lines containing two integers $X_{j}$ and $Y_{j}$: coordinates of point number $j$ ($- 10^5 \le X_{j}, Y_{j} \le 10^5,ドル 1ドル \le j\le N$). Set of points with integer coordinates may be answer for painter if all points have different coordinates and for any pair $(U_{i}, V_{i})$ coordinates of points $U_{i}$ and $V_{i}$ are neighbour on square plane.

제한

힌트