CF930C Teodor is not a liar!

小 Teodor 喜欢画画。他最喜欢的爱好是在他巨大的 $[1;m]$ 线段内画出若干端点为整数的线段。一天，Teodor 发现他刚画的图有一个有趣的特性：不存在一个整数点属于所有的线段。发现了这个事实后，Teodor 决定与 Sasha 分享。 Sasha 知道 Teodor 喜欢炫耀，所以他从不轻易相信他。Teodor 想证明自己有时是值得信任的，于是他决定说服 Sasha，证明在他的图中确实不存在一个属于所有线段的整数点。然而，Teodor 很懒，既不愿意告诉 Sasha 所有线段的端点坐标，也不愿意告诉他线段的数量，所以他建议 Sasha 可以问他一系列问题：“给定整数点 $x_i$，Teodor 的图中有多少条线段包含该点？”，并承诺会如实回答这些问题。 两个人都很忙，没有太多时间，所以他们请你帮忙计算：Sasha 最多可以问多少个不同的问题，使得仅凭这些问题的答案，Sasha 仍然无法确定 Teodor 是否在撒谎。注意，Sasha 并不知道 Teodor 图中线段的数量。当然，Sasha 很聪明，绝不会重复询问同一个点。

输入的第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 100000$），分别表示 Teodor 图中线段的数量和 Sasha 可以询问的最大点的坐标。 接下来的 $n$ 行中，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$（$1 \leq l_i \leq r_i \leq m$），表示第 $i$ 条线段的左端点和右端点。注意，线段的左右端点可以是同一个点。 保证不存在一个整数点属于所有线段。

输出一行一个整数 $k$，表示最大的集合大小 $ (x_i, cnt(x_i)) $，其中所有 $x_i$ 互不相同，$1 \leq x_i \leq m$，$cnt(x_i)$ 表示包含坐标为 $x_i$ 的点的线段数量，使得仅凭这些信息（且不知道 $n$），Sasha 仍无法确定 Teodor 是否在撒谎。

第一个样例展示了这样一种情况：Sasha 无法确定 Teodor 是否在撒谎，因为即使他知道区间 $[1;4]$ 内每个点的 $cnt(x_i)$，他也无法区分 Teodor 画的是这些线段，还是整个 $[1;4]$ 这一条线段。 在第二个样例中，Sasha 可以询问 5 个点，例如 $1,2,3,5,6$，仍然无法确定 Teodor 是否在撒谎。但一旦他知道了 $[1;6]$ 区间内所有点的信息，他就可以确定 Teodor 没有撒谎。 由 ChatGPT 4.1 翻译