题目描述

某省骨干网中部署了多台核心路由器。为提升运维效率，要把这些地理位置分散的设备在逻辑上划成 $N$ 个管理域，并尽量让同一域内的设备彼此靠近，便于统一调度。

划分采用 Bi-K-means（二分 K-means）：一开始把全部设备看成一个簇 $C_0$，之后反复分裂当前最适合的簇，直到簇的个数等于 $N$。

SSE（误差平方和）定义为

其中 $\mu$ 是簇 $C$ 的质心（各点坐标的算术平均）。将一个父簇裂成两个子簇时，SSE 下降量为

每一次从当前簇集合里选出一个簇，对其做 $K=2$ 的 K-means 分裂，规则如下：

1. 优先选择 $SSE\_Grad$ 最大的簇；若下降量相同，选择设备数更多的簇；若设备数也相同，选择生成时间更早的簇。初始簇 $C_0$ 的生成时间最早；每次分裂得到的两个子簇按「先归入 $x$ 最小初始质心一侧、后归入 $x$ 最大初始质心一侧」依次生成，且都晚于其父簇。
2. 对选中的簇做 2-means 时，必须取该簇内 $x$ 坐标最小和 $x$ 坐标最大的两个设备作为初始质心，禁止随机初始化。
3. 若某设备到两个质心的欧氏距离相等，则划入 $x$ 坐标较小的那个初始质心所在簇。
4. 2-means 在下列任一条件成立时停止：两个新质心的最大偏移量（欧氏距离）小于 $1e-6$；或所有设备的簇归属不再变化。
5. 外层分裂进行到簇数等于 $N$ 为止。第 $0$ 次结果是尚未分裂的初始簇。

输入描述

第一行一个整数 $N$，表示期望得到的管理域（簇）个数，满足 $1\le N\le 20$。

第二行一个整数 $L$，表示核心路由器台数，满足 $1\le L\le 100$。

随后 $L$ 行，每行两个整数 $x$ $y$，表示一台路由器的二维坐标（经度、纬度）。坐标均为整数，满足 $0\le x,y\le 1000$，且不同路由器的 $x$ 坐标互不相同。

输出描述

输出 Bi-K-means 每一轮分裂后，当前各簇设备数的降序序列。初始簇 $C_0$ 的设备数作为第 $0$ 次的结果。共输出 $N$ 行，第 $i$ 行对应已经得到 $i+1$ 个簇时的规模列表（同一行内以空格分隔）。

样例1

输入

3
4
0 0
1 0
8 0
9 1

输出

4
2 2
2 1 1

说明

$4$ 个点要划成 $3$ 个管理域。

第 $0$ 次：尚未分裂，只有 $C_0$，设备数为 $4$。

第 $1$ 次：对 $C_0$ 做 2-means，初始质心取 $x$ 最小的 $(0,0)$ 与 $x$ 最大的 $(9,1)$。归属稳定后得到两个规模为 $2$ 的簇：$\lbrace(0,0),(1,0)\rbrace$ 与 $\lbrace(8,0),(9,1)\rbrace$，降序为 $2\ 2$。

第 $2$ 次：左簇质心为 $(0.5,0)$，$SSE=0.5$，裂成两个单点后 $SSE\_Grad=0.5$；右簇质心为 $(8.5,0.5)$，$SSE=1$，裂成两个单点后 $SSE\_Grad=1$。应分裂右簇，规模变为 $2,1,1$，降序为 $2\ 1\ 1$。

样例2

输入

1
3
4 2
7 9
11 3

输出

3

说明

$N=1$，不需要分裂，直接输出初始簇的设备数 $3$。