CF1068C.Colored Rooks

Ivan is a novice painter. He has $n$ dyes of different colors. He also knows exactly $m$ pairs of colors which harmonize with each other.

Ivan also enjoy playing chess. He has $5000$ rooks. He wants to take $k$ rooks, paint each of them in one of $n$ colors and then place this $k$ rooks on a chessboard of size $10^{9} \times 10^{9}$.

Let's call the set of rooks on the board connected if from any rook we can get to any other rook in this set moving only through cells with rooks from this set. Assume that rooks can jump over other rooks, in other words a rook can go to any cell which shares vertical and to any cell which shares horizontal.

Ivan wants his arrangement of rooks to have following properties:

• For any color there is a rook of this color on a board;
• For any color the set of rooks of this color is connected;
• For any two different colors $a$ $b$ union of set of rooks of color $a$ and set of rooks of color $b$ is connected if and only if this two colors harmonize with each other.

Please help Ivan find such an arrangement.

伊万是一名初学绘画的新手。他有 $n$ 种不同颜色的颜料，还精确地知道 $m$ 对彼此协调的颜色。

伊万也喜欢下国际象棋。他拥有 5000 枚车（rook）。他想从中选出 $k$ 枚车，将每枚车涂上 $n$ 种颜色之一，然后将这 $k$ 枚车放置在一块大小为 $10^{9} \times 10^{9}$ 的棋盘上。

我们称棋盘上的一组车是连通的，如果对于该组中的任意两枚车，都存在一条路径，使得我们仅通过该组内的车所占据的格子即可从其中一枚车到达另一枚车（即路径上所有中间格子均被该组中的某枚车占据）。注意：车可以跳过其他车——换言之，一枚车可以移动到与其处于同一行或同一列的任意格子（不考虑中间是否有其他棋子阻挡）。

伊万希望他的车的布局满足以下条件：

• 每种颜色至少有一枚车被涂成该颜色并放置在棋盘上；
• 对于每种颜色，所有涂成该颜色的车所构成的集合是连通的；
• 对于任意两种不同的颜色 $a$ 和 $b$，颜色 $a$ 的车集合与颜色 $b$ 的车集合的并集是连通的，当且仅当颜色 $a$ 与颜色 $b$ 是彼此协调的。

请帮助伊万找到这样一种布局方案。

The first line of input contains $2$ integers $n$, $m$ ($1 \le n \le 100$, $0 \le m \le min(1000, \,\, \frac{n(n-1)}{2})$) — number of colors and number of pairs of colors which harmonize with each other.

In next $m$ lines pairs of colors which harmonize with each other are listed. Colors are numbered from $1$ to $n$. It is guaranteed that no pair occurs twice in this list.

输入的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 100$，$0 \le m \le \min\left(1000, \,\, \frac{n(n-1)}{2}\right)$），分别表示颜色种数以及相互协调的颜色对数。

接下来的 $m$ 行中，每行列出一对相互协调的颜色。颜色编号为 $1$ 到 $n$。保证该列表中不会出现重复的配对。

Print $n$ blocks, $i$-th of them describes rooks of $i$-th color.

In the first line of block print one number $a_{i}$ ($1 \le a_{i} \le 5000$) — number of rooks of color $i$. In each of next $a_{i}$ lines print two integers $x$ and $y$ ($1 \le x, \,\, y \le 10^{9}$) — coordinates of the next rook.

All rooks must be on different cells.

Total number of rooks must not exceed $5000$.

It is guaranteed that the solution exists.

输出 $n$ 个块，其中第 $i$ 个块描述第 $i$ 种颜色的车。

在每个块的第一行输出一个整数 $a_{i}$（$1 \le a_{i} \le 5000$），表示第 $i$ 种颜色的车的数量。接下来的 $a_{i}$ 行中，每行输出两个整数 $x$ 和 $y$（$1 \le x, \,\, y \le 10^{9}$），表示一辆车的坐标。

所有车必须位于互不相同的格子上。

车的总数不得超过 $5000$。

保证存在满足条件的解。

Rooks arrangements for all three examples (red is color $1$, green is color $2$ and blue is color $3$).

所有三个示例中的车（Rook）摆放方案（红色为颜色 $1$，绿色为颜色 $2$，蓝色为颜色 $3$）。