问题 25862 --爆破VS凤凰

25862: 爆破VS凤凰

时间限制: 1 Sec  内存限制: 128 MB
提交: 38  解决: 13
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][132kb]

题目描述

Er-pang又跟生哥去网吧打LOL(英雄联盟),er-pang还是用他最爱的爆破鬼才-吉格斯,生哥还是用他花重金买下的冰晶凤凰-艾尼维亚。每次生哥都被虐的很惨。

生哥终于忍不住了,他居然开挂了!

开了挂后的凤凰越飞越高,居然还出现了n-1个幻象(逆天了),加上本尊一共n个凤凰在天上乱飞。由于爆破鬼才的视力极好,可以在瞬间扔出炸弹并炸死凤凰或是幻象。所以我们可以看做三维立体空间中有n个不动的凤凰,每个凤凰有一个坐标(xyz)。爆破鬼才的炸弹爆炸后不会消失,而且还会跳跃,但仅能跳到更高的地方。即如果炸弹当前处在(x1y1z1),当且仅当x2>x1y2>y1z2>z1时,它会跳到(x2y2z2)。

举个例子:凤凰在(000) (110) (111) (222)时

一个合法的炸弹弹跳序列是{1,3,4}

一个不合法的炸弹弹跳序列是{1,2,4}

现在告诉你n个凤凰的精确位置,问你两个问题:

1.  爆破鬼才扔出一个炸弹最少能炸死多少凤凰

2.  爆破鬼才至少需要扔出多少个炸弹才能将凤凰全部炸死


输入

第一行一个整数为n,表示天空中有n个凤凰。

接下来的n行每行有三个非负整数xiyizi表示凤凰的位置,保证任意两个凤凰不会出现在同一位置。

输出

输出文件有且仅有两行。

第一行输出一个整数表示一个炸弹最多能炸死多少个凤凰

第二行输出一个整数表示至少需要多少个炸弹才能炸死全部的凤凰

样例输入

4
0 0 0
1 1 0
1 1 1
2 2 2

样例输出

3
2

提示


所有坐标都是0~1000000的整数



30% n<=30



50% n<=100


100%
n<=1000

来源

[提交][状态]