은하 충돌

안드로메다 은하는 약 38억 년 뒤에 우리 은하와 충돌할 것으로 예상된다. 두 은하에 속한 별 사이의 거리가 워낙 멀기 때문에, 이 충돌은 별끼리 부딪치는 사건이 아니라 두 은하가 하나로 합쳐지는 과정에 가깝다. 앤드루 교수는 충돌의 결과를 예측하는 계산 모형을 만들고 있고, 당신의 도움이 필요하다.

이미 합쳐진 은하의 어떤 영역에 있는 별을 2차원 평면 위의 점으로 나타낸 집합이 주어진다. 각 별이 원래 어느 은하에서 왔는지는 알 수 없다. 다만 이 영역에서는 같은 은하에서 온 두 별 사이의 거리가 항상 5광년보다 크다는 사실이 알려져 있다.

이 영역의 별은 모두 안드로메다 은하나 우리 은하에서 왔으므로, 주어진 점 집합은 서로소인 두 부분집합으로 나뉘고 각 부분집합 안에서 두 점 사이의 최소 거리는 5광년보다 크다. 교수는 이런 분할을 좋은 분할이라고 부른다. 좋은 분할은 여러 가지일 수 있다. 모든 좋은 분할을 통틀어 한 부분집합이 가질 수 있는 점 개수의 최솟값을 구하는 프로그램을 작성하시오.

첫 번째 예제의 점 여섯 개에는 좋은 분할이 네 가지 있다. {1, 2, 4, 5}와 {3, 6}, {1, 2, 3, 4}와 {5, 6}, {1, 4, 5}와 {2, 3, 6}, {1, 3, 4}와 {2, 5, 6}이며, 번호는 입력에 주어진 순서를 뜻한다. 따라서 한 부분집합이 가질 수 있는 점 개수의 최솟값은 2이고, 안드로메다 은하에서 온 별은 적어도 두 개다.

첫째 줄에 점의 개수 $N$ ($1 \le N \le 5 \times 10^4$)이 주어진다. 다음 $N$개 줄에는 각 점의 좌표를 나타내는 두 정수 $X$와 $Y$ ($1 \le X, Y \le 5 \times 10^5$)가 주어지며, 단위는 광년이다. 같은 점이 두 번 주어지는 경우는 없고, 주어진 집합에는 좋은 분할이 적어도 하나 존재한다.

좋은 분할에서 한 부분집합이 가질 수 있는 점 개수의 최솟값을 한 줄에 출력한다.