Inna非常爱睡觉,所以她总共需要n个闹钟才能醒来。假设 Inna 的房间是一个 100 × 100 的正方形,左下角位于点 (0, 0),右上角位于点 (100, 100)。那么闹钟就是这个正方形中具有整数坐标的点。
早晨已经到来。 Inna 房间里所有的 n 个闹钟都响了,所以 Inna 想把它们关掉。为此,Inna 想出了一个有趣的游戏:
- 首先 Inna 选择她将在整个游戏中使用的片段类型。这些段可以是垂直的或水平的。
- 然后 Inna 做出了多个动作。伊娜只需一步即可在平面上画出任意长度的线段,她在游戏开始时选择其类型(垂直或水平),然后该线段上的所有闹钟都会关闭。当所有闹钟都关闭时游戏结束。
Inna 很困,所以她想尽快打完闹钟。帮助她,找到她在游戏中关闭所有闹钟所需的最少步数!
输入
输入的第一行包含整数 n (1 ≤ n ≤ 105) — 闹钟的数量。接下来的 n 行描述时钟:第 i 行包含两个整数 xi, yi — 第 i 个闹钟的坐标 (0 ≤ xi, yi ≤ 100)。
请注意,房间中的单个点可以包含任意数量的闹钟,并且闹钟可以位于代表房间的正方形的两侧。
输出
在一行中打印一个整数——如果 Inna 表现最佳,她必须绘制的最小线段数。
示例
输入 #1
4 0 0 0 1 0 2 1 0
输出 #1
2
输入 #2
4 0 0 0 1 1 0 1 1
输出 #2
2
输入 #3
4 1 1 1 2 2 3 3 3
输出 #3
3
注意
在第一个示例中,Inna 首先选择类型“垂直线段”,然后她制作末端为:(0, 0), (0, 2) 的线段;以及,例如,(1, 0)、(1, 1)。如果她画水平线段,她将需要至少 3 个线段。
在第三个示例中,值得注意的是 Inna 无权在游戏过程中更改片段的类型。这就是为什么她需要 3 个水平部分或 3 个垂直部分才能结束游戏。