시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 72 | 54 | 52 | 77.612% |
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.
3 1 1 2 3 2 2
2
8 0 1 1 7 4 8 3 7 1 2 4 5 3 7 1 8
-1