소 장애물 경주

문제

농부 존(FJ)은 다음 인기 관람 스포츠로 소 장애물 경주(Cow Steeplechase)라는 기발한 아이디어를 떠올렸습니다! 잘 알려진 대로, 일반적인 장애물 경주(steeplechase)는 여러 마리의 말이 뛰어넘어야 하는 장애물로 가득한 코스를 도는 경기입니다. FJ는 장애물을 충분히 낮게 만들기만 하면 잘 훈련된 소로도 같은 경기를 할 수 있다고 생각합니다.

코스를 설계하기 위해 FJ는 설치할 수 있는 모든 장애물 후보 $N$개($1 \le N \le 250$)를 그림으로 그립니다. 각 장애물은 2차원 평면 위에서 가로축 또는 세로축에 평행한 하나의 선분으로 표현됩니다. 장애물 $i$는 서로 다른 두 끝점 $(X1_i, Y1_i)$와 $(X2_i, Y2_i)$를 가지며, $1 \le X1_i, Y1_i, X2_i, Y2_i \le 10^9$입니다. 예시 배치는 다음과 같습니다.

   --+-------   
-----+-----
  ---+---     |
     |     |  |
   --+-----+--+-   |
     |     |  |  | |
     |   --+--+--+-+-
           |  |  | |
              |

FJ는 어떤 두 장애물도 서로 교차하지 않는다는 조건 아래에서 가능한 한 많은 장애물을 설치하려고 합니다. 위 그림에서 시작하면 FJ는 7개의 장애물을 설치할 수 있습니다.

   ----------   
-----------
  -------     |
           |  |
           |  |    |
           |  |  | |
           |  |  | |
           |  |  | |
              |

두 선분은 단 한 점이라도 공유하면 교차하는 것으로 간주하며, 그 점이 한쪽 또는 양쪽 선분의 끝점이어도 마찬가지입니다. 입력에서 어떤 두 수평 선분도 서로 교차하지 않고, 마찬가지로 어떤 두 수직 선분도 서로 교차하지 않는다고 가정해도 됩니다.

FJ가 설치할 수 있는 장애물의 최대 개수를 구하세요.

입력

첫째 줄: 정수 $N$ 하나.
둘째 줄부터 $N+1$째 줄까지: $i+1$째 줄에는 장애물 $i$를 나타내는 네 정수 $X1_i$, $Y1_i$, $X2_i$, $Y2_i$가 공백으로 구분되어 주어집니다.

출력

첫째 줄: FJ가 선택할 수 있는, 서로 교차하지 않는 선분의 최대 개수.

힌트

예시에는 세 개의 장애물 후보가 있습니다. $(4, 5)$에서 $(10, 5)$까지의 수평 선분 하나와, $(6, 2)$에서 $(6, 12)$까지, 그리고 $(8, 3)$에서 $(8, 5)$까지의 수직 선분 두 개입니다. 수평 선분이 두 수직 선분 모두와 교차하므로 최대 두 개의 장애물만 설치할 수 있습니다. 서로 교차하지 않는 두 수직 선분을 선택하면 최적해인 2를 얻습니다.