P8858.md

折线

题目描述

平面直角坐标系的第一象限内有一块左下角为 $(0,0)$ 右上角为 $(10^{100},10^{100})$ 的矩形区域，区域内有正偶数个整点，试求出这样一条从 $(0,0)$ 出发，到 $(10^{100},10^{100})$ 的在区域内部的折线：

• 折线的每一部分都平行于 $x$ 轴或 $y$ 轴。
• 折线不能经过给定的整点。
• 折线将整块区域分成包含给定整点个数相等的两块。
• 折线拥有尽可能少的折点。

可以证明一定存在一条满足限制的折线，你只需要输出满足限制的折线的折点数即可。

注意折点的坐标可以不是整数。

输入格式

输入第一行一个正整数 $T$，表示数据组数。

接下来的每组数据中，第一行一个正偶数 $n$，表示给定的整点个数。

接下来 $n$ 行，第 $i$ 行两个正整数 $x_i,y_i$，表示给定的第 $i$ 个整点的坐标为 $(x_i,y_i)$。

输出格式

输出 $T$ 行，每行一个正整数，表示满足限制的折线的折点数。

样例 #1

样例输入 #1

3
4
1 1
1 2
4 1
4 2
6
1 2
1 3
2 1
2 2
2 3
3 2
12
1 3
2 2
2 3
2 4
3 1
3 2
3 4
3 5
4 2
4 3
4 4
5 3

样例输出 #1

2
3
4

提示

【样例解释】

对于第一组数据，一条合法的折线为：$(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$ 为正偶数，每组数据中不存在两个坐标相同的整点。