Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Line Segment Erase
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 1533Accepted: 440

Description

Bob has drawn some line segments on the x-axis. But he is unsatisfied with his work, because some line segments overlap with others. So he decides to erase some of them so that none of them overlaps with others. Of course, Bob only wants to erase the minimum number of line segments. Clever Bob quickly finds a method to do this, but now he wants to know how many different choices he has to remove the overlapping?

Input

The input contains multiple test cases. For each test case, it consists of M + 1 lines:
Line 1: a single positive integer M (M <= 80), indicating the number of line segments Bob has drawn.
Line 2 to M +1: each contains two different integers S, E (-10000 <= S, E <=10000), indicating the two end positions of a line segment.

Output

Output the number of sticks Bob will erase and the number of different choices in a single line, separated by a single space.

Sample Input

5
1 3
3 5
4 6
8 9
4 6
1
1 3

Sample Output

2 3
0 1

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator