겹치는 회의

시간 제한2초메모리 제한1024 MB

요약

n개의 구간이 주어집니다. 겹치는 두 구간을 합치는 연산으로 모든 구간과 겹치는 구간 수의 최솟값을 줄이는 데 필요한 최소 연산 횟수를 구합니다.

난이도: 어려움10점 중 8점
유형: 구간, 그리디, 동적 계획법
정답자: 아직 제출이 없습니다

문제

Lucy는 매우 게으르다. 상사는 그녀가 학회에서 가능한 한 많은 회의에 참석하기를 바란다. 그러나 Lucy는 참석하지 않는 모든 회의가 그녀가 참석하는 회의 가운데 적어도 하나와 겹치도록 회의를 고른다. 그러면 더 이상 참석할 수 있는 회의가 없으므로 상사는 불평할 근거가 없다.

학회 운영진 중 한 명인 Max는 시간표를 담당한다. 그는 회의를 취소하거나 일정을 바꿀 수 없지만, 겹치는 두 회의를 하나로 합칠 수는 있다. 두 회의 $a$ 와 $b$ 는 $\text{start}(a) \le \text{start}(b) \le \text{end}(a)$ 또는 $\text{start}(b) \le \text{start}(a) \le \text{end}(b)$ 이면 겹친다고 한다. 합쳐진 회의는 $\min(\text{start}(a),\text{start}(b))$ 에 시작해서 $\max(\text{end}(a),\text{end}(b))$ 에 끝난다. 합쳐진 회의는 다른 회의와 다시 합칠 수 있다. 겹치지 않는 회의는 합칠 수 없다.

Lucy는 합치는 방법으로 자신이 참석해야 하는 회의 수를 줄일 수 있는지 알고 싶다. 줄일 수 있다면, 그 수를 적어도 하나 줄이는 데 필요한 합치기 횟수는 몇 번인가?

입력

첫 줄에 회의의 수인 정수 $n$ ( $2 \leq n \leq 10^6$ )이 주어진다. 이어지는 $n$ 개의 줄에는 각각 두 정수 $a$ 와 $b$ ( $0 \leq a \leq b \leq 10^9$ )가 주어진다. $a$ 는 회의의 시작 시각이고 $b$ 는 종료 시각이다.

출력

Lucy가 참석해야 하는 회의 수를 줄일 수 있다면, 그 수를 줄이는 데 필요한 합치기 연산의 최소 횟수를 출력한다. 줄일 수 없다면 impossible을 출력한다.

예제3

예제 1
입력
```
4
1 3
2 5
4 7
6 9
```
예상 출력
```
1
```
예제 2
입력
```
5
1 3
4 7
8 10
2 5
6 9
```
예상 출력
```
2
```
예제 3
입력
```
3
1 2
2 3
3 4
```
예상 출력
```
impossible
```