CF690B3 Recover Polygon (hard)

僵尸们发现了僵尸感染程度检测器，并设法破坏了它！现在，检测它们主巢穴的形状对 Heidi 来说将是一个真正的挑战。和以前一样，巢穴可以用网格上的严格凸多边形来表示。多边形的每个顶点都占据网格上的一个点。然而，受损的僵尸感染程度检查器只能判断每个单元格的僵尸感染程度是否在以下集合中：$\{1,2,3\}$。换句话说，Heidi 知道所有位置僵尸感染程度不为 $0$ 和 $4$。 有了这些信息，Heidi 还想知道巢穴的准确形状，以便对僵尸带来的下一场浩劫。请帮帮她吧！

输入包含多组数据。 第一行输入两个以空格间隔的整数 $N$ 和 $M$，分别表示巢穴网格的大小 $(5\le N\le 100000)$ 以及巢穴网格中感染程度为 $1,2,3$ 的点的数量 $(8\le M\le 200000)$。 第二行输入 $M$ 对整数 $x_1,y_1,...,x_M,y_M$ $(1\le x_i,y_i\le N)$，表示僵尸感染程度不等于 $0$ 或 $4$ 的单元格坐标。每对坐标都互不相同。 单元格根据其右上角的坐标进行编号。这意味着与原点相接触的最下面最左边的单元格的坐标为 $(1,1)$，而最上面最左边的单元格被标识为 $(1,N)$。 输入文件的最后一行读入两个零。这一行不应被视为一组数据。一个文件中所有数据的 $M$ 值的总和不会超过 $200000$。

对于每组输入数据，按如下格式输出： 第一行应输出一个整数 $V$，表示秘密巢穴的多边形顶点数。接下来的 $V$ 行每行输出两个整数，按顺时针顺序输出多边形的顶点，从字典序最小的顶点开始。 ### **说明/提示** 保证存在唯一解决方案。保证在正确的解决方案中，多边形顶点的坐标在 $1$ 到 $N-1$ 之间。我们说一个顶点 $(x_{1},y_{1})$ 在字典序上小于顶点 $(x_{2},y_{2})$ 当且仅当 $x_1

It is guaranteed that the solution always exists and is unique. It is guaranteed that in the correct solution the coordinates of the polygon vertices are between $ 1 $ and $ N-1 $ . A vertex $ (x_{1},y_{1}) $ is lexicographically smaller than vertex $ (x_{2},y_{2}) $ if $ x_{1}