P8858 折线

平面直角坐标系的第一象限内有一块左下角为 $(0,0)$ 右上角为 $(10^{100},10^{100})$ 的矩形区域，区域内有**正偶数**个整点，试求出这样一条从 $(0,0)$ 出发，到 $(10^{100},10^{100})$ 的在区域内部的折线： - 折线的每一部分都平行于 $x$ 轴或 $y$ 轴。 - 折线不能经过给定的整点。 - 折线将整块区域分成包含给定整点个数相等的两块。 - 折线拥有尽可能少的折点。 可以证明一定存在一条满足限制的折线，你只需要输出满足限制的折线的折点数即可。 注意折点的坐标可以不是整数。

无

无

#### 【样例解释】 对于第一组数据，一条合法的折线为：$(0,0) \to (2.5,0) \to (2.5,10^{100}) \to (10^{100},10^{100})$，它有 $(2.5,0)$ 和 $(2.5,10^{100})$ 两个折点。 #### 【数据范围】 | 测试点编号 | $n \leq$ | 特殊限制 | |:-----------:|:--------:|:------------------:| | $1 \sim 2$ | $4$ | 无 | | $3 \sim 4$ | $10$ | 无 | | $5 \sim 6$ | $50$ | 无 | | $7 \sim 8$ | $10^5$ | 保证答案不大于 $3$ | | $9 \sim 10$ | $10^5$ | 无 | 对于所有数据，$1 \leq T \leq 10^4, 1 \leq \sum n \leq 5 \times 10^5, 1 \leq x_i,y_i \leq n$，保证 $n$ 为正偶数，每组数据中不存在两个坐标相同的整点。