题目描述

鲍勃在 $x$ 轴上画了一些线段，但他对自己的作品不满意，因为有些线段互相重叠。因此，他决定擦除其中的一些线段，使得剩下的线段互不重叠。当然，鲍勃希望擦除的线段数量最少。聪明的鲍勃很快找到了一种方法，但现在他想知道有多少种不同的选择可以达到这个目的？

输入格式

输入包含多个测试用例。每个测试用例由 $M + 1$ 行组成：

• 第1行：一个正整数 $M$（$M \leq 80$），表示鲍勃画的线段数量。
• 第2行到第 $M+1$ 行：每行包含两个不同的整数 $S$ 和 $E$（$-10000 \leq S, E \leq 10000$），表示一条线段的两个端点坐标。

输出格式

对于每个测试用例，输出一行两个整数，分别表示鲍勃需要擦除的线段数量以及不同的选择方案数，中间用一个空格隔开。

示例输入

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

示例输出

2 3
0 1

来源

POJ Monthly--2005.08.28, Static