题目描述

有一个长度为 $N$ 的序列，$Q$ 次询问，每一次询问会覆盖到一个区间 $[L,R]$。

你需要构造一个二叉树，满足以下条件：

• 每个节点对应一个区间
• 根节点对应区间 $[1,N]$
• 叶子节点对应区间 $[i,i]$，同时对应区间 $[i,i]$ 的节点一定是叶子节点
• 每一个非叶子节点一定有两个子节点，如果一个非叶子节点对应 $[i,j]$，那么它的两个子节点对应区间分别为 $[i,k],[k+1,j](i \le k < j)$

对区间 $[L,R]$ 进行一次询问时，从根节点开始搜索，如果一个节点对应的区间被完全包含在 $[L,R]$ 中或该节点对应的区间与 $[L,R]$ 没有重叠，则不遍历其子节点，否则遍历其所有子节点。

记 $d$ 为遍历到的节点的最大深度，$c$ 为深度为 $d$ 的节点被遍历到的总次数，你需要在保证在 $d$ 最小的条件下 $c$ 最小，输出 $d$ 和 $c$。

translated by

/user/372622

输入格式

第一行两个整数 $N,Q$。

之后 $Q$ 行，每一行两个数 $L_i,R_i$，表示一次询问。

输出格式

一行两个数 $d,c$，表示答案。

样例 1

输入

6 4
2 3
3 4
2 4
3 3

输出

3 4

样例 2

输入

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

输出

4 4

说明/提示

$2 \le N \le 4000,1 \le Q \le 10^5,1 \le L\_i \le R\_i \le N(1\le i \le Q)$