Rooks Game 是一个单人游戏，使用一个 $N \times N$ 的棋盘和 $M$ 个车。

车可以在水平或垂直方向上穿过任意数量的空位进行移动。当一个车可以攻击另一个车时，它可以吃掉该车并移动到被吃掉的车所在的方格。注意，在 Rooks Game 中，我们不区分黑白，换句话说，每个车都可以吃掉其他任何车。

初始时，棋盘上有 $M$ 个车。在每一步中，一个车吃掉另一个车。玩家重复进行吃子操作，直到没有任何车可以被吃掉为止。这个游戏有两个目标：一个是最小化被吃掉的车数，另一个是最大化被吃掉的车数。

在本题中，你需要计算被吃掉的车数的最小值和最大值。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示棋盘的大小和车的数量 ($1 \le N, M \le 1000$)。接下来的 $M$ 行给出了每个车的位置。第 $i$ 行包含 $x_i$ 和 $y_i$，表示第 $i$ 个车位于第 $x_i$ 列和第 $y_i$ 行 ($1 \le x_i, y_i \le N$)。你可以假设任意两个车不在同一个位置。

输出格式

输出被吃掉的车数的最小值和最大值，中间用一个空格隔开。

样例

样例输入 1

8 3
1 1
1 8
8 8

样例输出 1

1 2

样例输入 2

8 4
1 1
1 8
8 8
8 1

样例输出 2

2 3

样例输入 3

5 5
1 1
2 2
3 3
4 4
5 5

样例输出 3

0 0

样例输入 4

100 1
100 100

样例输出 4

0 0

样例输入 5

10 12
1 2
1 4
1 6
3 6
5 6
10 7
8 7
6 7
4 7
2 7
7 3
9 5

样例输出 5

7 8