마법 타일 제거

Ayimok은 마법사이다.

그의 일상은 마법 타일을 한 줄로 배치한 뒤 마법을 거는 것이다.

마법 타일과 그 배치에는 다음과 같은 규칙이 있다.

• 각 마법 타일은 높이가 1인 사다리꼴 모양이다.
• 어떤 마법 타일은 다른 마법 타일과 겹칠 수 있다.
• 마법 타일은 2차원 좌표계 위에 배치된다.
• 마법 타일의 윗변은 y 좌표가 1인 수평선 위에 있다.
• 마법 타일의 아랫변은 y 좌표가 0인 수평선 위에 있다.

그는 마법을 다 건 뒤에는 이 마법 타일들을 치워야 한다. 어느 날, 타일을 하나씩 치우는 일이 너무 힘들었던 그는 그 과정을 간단하게 만들기로 했다.

그래서 마법 타일을 효율적으로 제거하는 "자화 마법"을 익혔다. 이 마법은 한 번에 마법 타일 여러 개를 제거한다. 이때 제거되는 타일들 중 어느 두 개를 골라도 서로 겹쳐야 한다.

예를 들어, 그림 1에서는 세 마법 타일이 모두 서로 겹치므로 세 개에 한 번에 자화 마법을 걸어 제거할 수 있다. (이해를 돕기 위해 타일의 높이는 일부러 다르게 그려져 있다.)

그림 1: 한 번에 제거할 수 있는 마법 타일들

하지만 그림 2에서는 타일 1과 타일 3이 겹치지 않으므로 세 마법 타일에 한꺼번에 자화 마법을 걸 수 없다.

그림 2: 한 번에 제거할 수 없는 마법 타일들

그는 자화 마법을 걸 때 마력이 많이 들기 때문에, 최소 횟수의 자화 마법으로 모든 마법 타일을 제거하고 싶다.

그림 3의 경우를 보자. 자화 마법을 세 번 걸어 모든 마법 타일을 제거할 수 있다. 첫 번째 마법은 타일 1과 2에, 두 번째 마법은 타일 3과 4에, 세 번째 마법은 타일 5와 6에 건다.

그림 3: 모든 마법 타일을 제거하는 방법 (최소 횟수가 아님)

사실 자화 마법을 두 번만 걸어 모든 마법 타일을 제거할 수 있다. 첫 번째 마법은 타일 1, 2, 3에, 두 번째 마법은 타일 4, 5, 6에 건다. 이것이 모든 마법 타일을 제거하는 데 필요한 최소 횟수이다.

그림 4: 모든 마법 타일을 제거하는 최적의 방법 (최소 횟수의 마법)

마법 타일 집합이 주어졌을 때, 모든 마법 타일을 제거하는 데 필요한 최소 자화 마법 횟수를 출력하는 프로그램을 작성하시오.

다른 타일과 겹치지 않는 마법 타일이 있을 수도 있지만, 그 타일을 제거하려면 그래도 자화 마법을 걸어야 한다.

입력은 다음 형식을 따른다.

N
xLower11 xLower12 xUpper11 xUpper12
xLower21 xLower22 xUpper21 xUpper22
xLower31 xLower32 xUpper31 xUpper32
:
:
xLowerN1 xLowerN2 xUpperN1 xUpperN2

첫째 줄에는 정수 N이 주어지며, 이는 마법 타일의 개수이다.

그다음 N개의 줄에 마법 타일의 정보가 주어진다.

(i+1)번째 줄에는 네 정수 xLoweri1, xLoweri2, xUpperi1, xUpperi2가 주어지며, 이는 i번째 마법 타일의 꼭짓점이 (xLoweri1, 0), (xLoweri2, 0), (xUpperi1, 1), (xUpperi2, 1)에 있다는 뜻이다.

두 마법 타일이 꼭짓점을 공유하지 않는다고 가정해도 된다. 즉, 모든 xLowerij는 서로 다르고, 모든 xUpperij도 서로 다르다. 입력은 다음 제약 조건을 따른다.

• 1 ≤ N ≤ 105
• 1 ≤ xLoweri1 < xLoweri2 ≤ 109
• 1 ≤ xUpperi1 < xUpperi2 ≤ 109
• 모든 xLowerij는 서로 다르다.
• 모든 xUpperij는 서로 다르다.

모든 마법 타일을 제거하는 데 필요한 최소 자화 마법 횟수를 출력한다.