x 축상에 선분의 시작점과 끝점이 주어질 때 이 선분들이 겹치지 않고 최대로 많은 선분을 만들기 위해 지워야 할 최소 선분의 수와 지울수 있는 방법의 수를 구하는 문제

입력의 예에서 5 개의 선분 이 주어진 경우

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

겹치지 않고 최대로 놓을 수 있게하기 위해 2 개의 선분을 지우면 되고 , 교차하지 않는 선분 3 개를 만드는 방법의 수가 3 가지이다.

입력

• 첫 줄은 선분의 수로 정수 M(M <= 80 ) 이 주어지고 ,
• 다음 M 라인은 선분의 시작점 S 와 끝 점 E (-10000 <= S, E <=10000)가 주어진다. S 와 E 는 서로 다른 점이다.

출력

입출력 예

입력

5
1 3
3 5
4 6
8 9
4 6

출력

2 3

입력

1
1 3

출력

0 1

출처:POJ Monthly--2005.08.28,Static