UVA1707 Surveillance

国际保护与控制组织（International Corporation for Protection and Control, ICPC）致力于开发高效的用于保护与控制的技术。自然而然，他们迫切希望自己的总部能够得到保护和监控。从上向下看，总部大楼是一个凸多边形的样子。在其周围有几个合适的位置可以安装摄像头来监视大楼。每个摄像头根据其位置，可以覆盖特定的多边形范围（即建筑墙壁）的边。ICPC 希望最小化覆盖整个建筑所需的摄像头数量。

输入包含多个测试样例，每个测试样例描述如下。 第一行包含两个整数 $ n $ 和 $ k $（$ 3 \leq n \leq 10^6 $ 和 $ 1 \leq k \leq 10^6 $），其中 $ n $ 是墙壁的数量，$ k $ 是可能安装摄像头的位置数量。接下来的 $ k $ 行每行包含两个整数 $ a_i $ 和 $ b_i $（$ 1 \leq a_i, b_i \leq n $）。表示安装在位置 $ i $ 的摄像头将覆盖哪些墙壁。如果 $ a_i \leq b_i $，则摄像头将覆盖每个满足 $ a_i \leq j \leq b_i $ 的墙壁 $ j $。如果 $ a_i > b_i $，则摄像头将覆盖每个满足 $ a_i \leq j \leq n $ 或 $ 1 \leq j \leq b_i $ 的墙壁 $ j $。

对于每组测试用例，单独占一行。 输出足以覆盖建筑物每一面墙的最小摄像头数量。两个摄像头覆盖的范围可以重叠。若无法覆盖整个建筑，输出 `impossible`。

_翻译由 deepseek 辅助生成_