Problem
격리된 상태에서 물리학 연구에 몰두한 소들은 "mu-입자"를 발견했습니다.
그들은 현재 N개의 "mu-입자"를 실험하고 있습니다. (1 ≤N ≤ 10
5). 입자 i에는 -10
9…10
범위의 두 정수 xi 및 yi로 설명되는 "스핀"이 있습니다. 9 포함. 때때로 두 개의 "mu-입자" 상호작용하다 이것은 스핀이 (x
i,y
i) 및 (x
j,y
j ) x
i≤x
j 및 y
i≤y
j가 있습니다. 이러한 조건에서 이러한 입자 중 정확히 하나가 사라지고 다른 입자에는 아무 일도 일어나지 않습니다. 주어진 시간에 최대 하나의 상호작용이 발생할 수 있습니다.
소는 임의의 일련의 상호 작용 후에 남아 있을 수 있는 "뮤 입자"의 최소 수를 알고 싶어합니다.
입력
첫 번째 줄에는 "mu-입자"의 초기 수인 하나의 정수 N이 포함됩니다. 다음 N 줄 각각에는 이 입자의 스핀을 정의하는 두 개의 공백으로 구분된 정수가 포함되어 있습니다. 모든 스핀이 다릅니다.
출판물
하나의 정수, 임의의 일련의 상호 작용 후에 남을 수 있는 "mu-입자"의 최소 수입니다.
예
<헤드>
| # |
입력 |
출력 |
참고 |
<몸>
| 1 |
4
10
0 1
-10
0 -1
| 1 |
가능한 상호작용 순서 중 하나:
입자 1과 4가 상호 작용하고 입자 1이 사라집니다.
입자 2와 4가 상호 작용하고 입자 4가 사라집니다.
입자 2와 3이 상호 작용하고 입자 3이 사라집니다.
입자 2만 남습니다. |
| 2 |
3
0 0
1 1
-1 3
| 2 |
입자 3은 다른 입자와 상호 작용할 수 없으므로 남아 있어야 합니다. 입자 1과 2 중 하나도 남아 있어야 합니다. |