僵尸已经发现了僵尸污染等级检查器并设法损坏了它!现在,检测其主要化合物的形状对海蒂来说将是一个真正的挑战。和以前一样,巢穴可以表示为晶格上的严格凸多边形。多边形的每个顶点占据晶格上的一个点。然而,受损的僵尸污染水平检查器只能判断每个单元格的僵尸污染水平是否在集合{1,2,3}中。换句话说,海蒂知道晶格中污染级别不为 0 也不为 4 的所有单元格。
有了这些信息,海蒂仍然想知道巢穴的确切形状,以便对僵尸进行毁灭性的打击。帮助她!
输入
输入包含多个测试用例。
每个测试用例的第一行包含两个空格分隔的整数 N 和 M,其中 N 是晶格网格的大小 (5 ≤ N ≤ 100000),M 是僵尸污染级别为 1、2 或 3 的晶格点的数量 (8 ≤ M ≤ 200000)。
每个测试用例的第二行包含 M 对整数 x1, y1, ..., xM, yM – 僵尸污染级别不等于 0 也不等于 4 的单元格的坐标。保证 1 ≤ xi, yi ≤ N。所有对 xi, yi 都不同。
单元格根据其右上角的坐标进行枚举。这意味着接触原点的最左下角单元格的坐标为 (1, 1),最左上角单元格的坐标为 (1, N)。
文件的最后一行包含两个零。该行不应被视为测试用例。一个文件中所有测试的 M 值总和不会超过 200000。
输出
对于每个测试用例,预期输出如下:
输出的第一行应包含一个整数 V,即秘密巢穴的多边形的顶点数。接下来的 V 行每条应包含两个整数,从字典顺序最小的顶点开始按顺时针顺序表示多边形的顶点。
示例
输入 #1
8 19 2 3 2 4 2 5 3 3 3 5 4 3 4 5 4 6 5 2 5 3 5 6 6 2 6 3 6 4 6 5 6 6 6 7 7 6 7 7 5 8 2 2 2 3 2 4 3 2 3 4 4 2 4 3 4 4 0 0
输出 #1
4 2 3 2 4 6 6 5 2 4 2 2 2 3 3 3 3 2
注意
保证解始终存在且唯一。保证在正确的解中,多边形顶点的坐标在 1 和 N - 1 之间。如果 x1 < x2 或 $$x_{1}=x_{2}\wedge y_{1}<y_{2}$$,则顶点 (x1, y1) 按字典顺序小于顶点 (x2, y2)。