グラフの空間への埋め込みとは、各頂点を空間内の異なる点に置き、各辺を両端の頂点を結ぶ単純な曲線として描くことで、共通の頂点以外では 2 つの曲線が交わらないようにすることである。この問題では、一定の条件を満たす三次元空間への埋め込みを考える。

$n$ 頂点 $m$ 辺の単純無向グラフが与えられる。これは、任意の 2 頂点を結ぶ辺が高々 1 本であり、各辺は異なる頂点を結ぶという意味である。頂点には $1$ から $n$、辺には $1$ から $m$ の番号が付いている。辺 $j$ は異なる頂点 $v_j$ と $w_j$ を結ぶ。各頂点に接続する辺は高々 5 本である。

次の条件をすべて満たすグラフの埋め込みを求めよ。

• 各頂点 $i$ は空間内の点 $(x_i,y_i,0)$ に埋め込む。座標 $x_i,y_i$ は $0$ 以上 $400$ 以下の整数でなければならない。すべての点は異なる座標を持たなければならない。

• 各辺 $j$ は、頂点 $v_j,w_j$ の埋め込み点を両端とする折れ線（連結した線分の列）として埋め込む。各線分は $x$ 軸、$y$ 軸、$z$ 軸のいずれかに平行でなければならない。折れ線の各節点の座標は $0$ 以上 $400$ 以下の整数でなければならない。各折れ線は両端を含め、高々 $30$ 個の節点を持つ。

• 折れ線は自己交差してはならない。異なる折れ線は、同じ頂点に接続する辺に対応する場合を除き、どの点も共有してはならない。その場合でも、その 1 つの端点だけを共有してよい。

入力

入力の最初の行には 2 つの整数 $n,m$ が与えられる（$2\le n\le1600$、$1\le m\le4000$）。続く $m$ 行のうち $j$ 行目には 2 つの整数 $v_j,w_j$ が与えられる（$1\le v_j<w_j\le n$）。

各頂点に接続する辺が高々 5 本であることが保証される。さらに多重辺はない。すなわち $j\ne j^{\prime}$ ならば $(v_j,w_j)\ne(v_{j^{\prime}},w_{j^{\prime}})$ である。

出力

まず $n$ 行を出力せよ。その $i$ 行目には頂点 $i$ を埋め込む位置を表す 2 つの整数 $x_i,y_i$ を出力せよ。続いて $m$ 行を出力せよ。その $j$ 行目は辺 $j$ に対応する折れ線を次の形式で表す。

$$k\ x^{\prime}_1\ y^{\prime}_1\ z^{\prime}_1\ \cdots\ x^{\prime}_k\ y^{\prime}_k\ z^{\prime}_k$$

ここで $k$ は節点数であり、$2$ 以上 $30$ 以下でなければならない。点 $(x^{\prime}_1,y^{\prime}_1,z^{\prime}_1),\ldots,(x^{\prime}_k,y^{\prime}_k,z^{\prime}_k)$ は折れ線の節点である。最初の点 $(x^{\prime}_1,y^{\prime}_1,z^{\prime}_1)$ は $(x_{v_j},y_{v_j},0)$、最後の点 $(x^{\prime}_k,y^{\prime}_k,z^{\prime}_k)$ は $(x_{w_j},y_{w_j},0)$ でなければならない。連続する各点を線分で結んで折れ線を作る。各線分の長さは正でなければならない。連続する 2 本の線分は同じ方向でもよく、例えば両方が $x$ 軸に平行でもよい。

出力する埋め込みは、上記のすべての条件を満たさなければならない。

与えられた入力制約のもとでは、少なくとも 1 つの有効な出力が存在することが示せる。複数の出力が存在する場合、そのどれも正解として認められる。

注記

特殊判定に関する注記：

ローカルでのテスト用のコマンドラインツールが提供される。DOMjudge からファイルをダウンロードできる。ツールの先頭に使い方を説明するコメントがある。

入出力例

入力 1

3 3
1 2
1 3
2 3

出力 1

0 0
400 0
0 399
3 0 0 0 100 0 0 400 0 0
4 0 0 0 0 0 200 0 399 200 0 399 0
3 400 0 0 400 399 0 0 399 0

注記

入出力例 1 の説明

図 B.1 は出力例で表される埋め込みを示す。

図 B.1：埋め込みの図。