시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 2 2 2 100.000%

문제

There are n people in a room, each of whom always tells the truth, or always lies. Each of them makes a statement of the form: “Some number between a and b (inclusive) of us are telling the truth.” What is the maximum number of truth-tellers in the room?

입력

Each input will consist of a single test case. Note that your program may be run multiple times on different inputs.

Each test case will begin with a line containing an integer n (1 ≤ n ≤ 1,000) which is the number of people in the room.

Each of the next n lines will have two space-separated integers, a and b (0 ≤ a ≤ b ≤ n). Each line represents the statement of one person that “Some number between a and b (inclusive) of us are telling the truth.”

출력

Output a single integer, which is the largest possible number of truth-tellers, or -1 if the statements are inconsistent.

예제 입력 1

3
1 1
2 3
2 2

예제 출력 1

2

예제 입력 2

8
0 1
1 7
4 8
3 7
1 2
4 5
3 7
1 8

예제 출력 2

-1