241999 - 花圃浇水记录

题目描述

学校把一条长花圃分成n个小格,从左到右编号为1至n。开始时所有小格都没有浇过水。

志愿者一共进行了m次浇水。每次给出两个编号l和r,表示从第l格到第r格的每一格都浇一次水,两个端点都包含。不同次浇水可能覆盖相同的小格,即使区间完全相同,也要分别计算次数。

请统计:全部浇水结束后,有多少格一次水也没浇过,又有多少格至少被浇过两次水。恰好被浇一次水的小格不计入这两个数量。

输入

第一行两个整数n、m,表示小格数量和浇水次数。

接下来m行,每行两个整数l、r,表示一次浇水的区间。当m=0时,没有后续区间。

【数据范围】

对全部数据,1 \le n \le 1000,0 \le m \le 1000;每次浇水满足1 \le l \le r \le n。

输出

输出两个整数,用一个空格隔开,依次表示从未被浇水的小格数量、至少被浇过两次水的小格数量。

样例

输入

5 3
1 3
3 5
2 4

输出

0 3

输入

6 2
2 2
2 4

输出

3 1
说明

【样例解释1】

五格的最终浇水次数依次为1、2、3、2、1。没有未浇水的小格,第2、3、4格至少被浇过两次,因此输出0 3。

【样例解释2】

六格的最终次数依次为0、2、1、1、0、0。第1、5、6格没有浇水,第2格被浇过两次,因此输出3 1。

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 17
通过人数 9
金币数量 2 枚
难度 入门


上一题 下一题