← 返回题目列表

Codeforces · 1068/C

C. 彩色车

中文机器翻译题面 查看原题

Ivan 是一位新手画家。他有 $$$n$$$ 不同颜色的染料。他还确切地知道 $$$m$$$ 相互协调的颜色对。

伊万也喜欢下棋。他有 $$$5000$$$ 车。他想要拿 $$$k$$$ 车,将它们分别涂成 $$$n$$$ 颜色之一,然后将这 $$$k$$$ 车放在尺寸为 $$$10^{9} \times 10^{9}$$$ 的棋盘上。

如果从任何车我们都可以到达该组中的任何其他车,并且仅通过该组中的车的单元格移动,那么我们称棋盘上的车组已连接。假设车可以跳过其他车,换句话说,车可以前往任何共享垂直方向的单元格和任何共享水平方向的单元格。

Ivan 希望他的车排列具有以下属性:

- 对于任何颜色,棋盘上都有一个该颜色的车;
- 对于任何颜色,该颜色的车组都是相连的;
- 对于任何两种不同的颜色 $$$a$$$ $$$b$$$,颜色为 $$$a$$$ 的车组和颜色为 $$$b$$$ 的车组的并集是连接的,当且仅当这两种颜色彼此协调时。

请帮助伊万找到这样的安排。

输入

输入的第一行包含 $$$2$$$ 整数 $$$n$$$, $$$m$$$ ($$$1 \le n \le 100$$$, $$$0 \le m \le min(1000, \,\, \frac{n(n-1)}{2})$$$) — 颜色数量和相互协调的颜色对数量。

在接下来的 $$$m$$$ 行中列出了相互协调的颜色对。颜色编号从 $$$1$$$ 到 $$$n$$$。保证没有任何对在此列表中出现两次。

输出

打印$$$n$$$块,其中第$$$i$$$描述了第$$$i$$$颜色的车。

在块打印的第一行中,有一个数字 $$$a_{i}$$$ ($$$1 \le a_{i} \le 5000$$$) — 颜色为 $$$i$$$ 的车的数量。在接下来的 $$$a_{i}$$$ 行中,打印两个整数 $$$x$$$ 和 $$$y$$$ ($$$1 \le x, \,\, y \le 10^{9}$$$) — 下一个车的坐标。

所有车必须位于不同的牢房中。

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

保证解存在。

示例

输入 #1

3 2
1 2
2 3

输出 #1

2
3 4
1 4
4
1 2
2 2
2 4
5 4
1
5 1

输入 #2

3 3
1 2
2 3
3 1

输出 #2

1
1 1
1
1 2
1
1 3

输入 #3

3 1
1 3

输出 #3

1
1 1
1
2 2
1
3 1

注意

Rooks 对所有三个示例的安排(红色是颜色 $$$1$$$,绿色是颜色 $$$2$$$,蓝色是颜色 $$$3$$$)。