#3902. 魔幻信封套娃-难

魔幻信封套娃-难

🐰😺🎎 兔猫信奥学院·魔幻信封套娃奇缘 🎎😺🐰

在兔猫信奥学院的奇幻工坊里,小兔和小猫正在研究一批神秘的魔法信封。每个信封都拥有独特的“宽度”与“高度”属性。传说,只有当一个信封的宽和高都严格小于另一个信封时,前者才能稳稳地“套”进后者,形成层层嵌套的“套娃”效果。

为了探索这批信封的奥秘,师傅留下一道试炼题:从这批信封中,最多能套出多少层信封? 你愿意接过这份挑战,帮他们揭开信封套娃的极限层数吗?


输入格式

第一行:整数 n,表示信封数量。
接下来 n 行,每行两个整数 w_i 和 h_i,分别表示第 i 个信封的宽度和高度。
  • 1n1051 \le n \le 10^5
  • 1wi,hi1051 \le w_i, h_i \le 10^5

输出格式

输出一个整数,表示最多能套出的信封层数。

样例 1

4
5 4
6 4
6 7
2 3
3
  • 解释:
    一种最优套法为:
    [2,3] → [5,4] → [6,7]
    
    共 3 层。

样例 2

3
1 1
1 1
1 1
1
  • 解释:
    所有信封同宽同高,任意信封只能独立成一层,最大层数为 1。