2922. Minimizing maximizer

单点时限: 5.0 sec

内存限制: 256 MB

The company Chris Ltd. is preparing a new sorting hardware called Maximizer. Maximizer has n inputs numbered from to . Each input represents one integer. Maximizer has one output which represents the maximum value present on Maximizer’s inputs.

Maximizer is implemented as a pipeline of sorters . Each sorter has inputs and outputs. sorts values on inputs in non-decreasing order and lets the other inputs pass through unchanged. The -th output of the last sorter is the output of the Maximizer.

An intern (a former ACM contestant) observed that some sorters could be excluded from the pipeline and Maximizer would still produce the correct result. What is the length of the shortest subsequence of the given sequence of sorters in the pipeline still producing correct results for all possible combinations of input values?

Write a program that:

reads a description of a Maximizer, i.e. the initial sequence of sorters in the pipeline, computes the length of the shortest subsequence of the initial sequence of sorters still producing correct results for all possible input data, writes the result.

输入格式

The first line of the input contains two integers and separated by a single space. Integer is the number of inputs and integer m is the number of sorters in the pipeline. The initial sequence of sorters is described in the next lines. The -th of these lines contains the parameters of the -th sorter: two integers and separated by a single space.

输出格式

The output consists of only one line containing an integer equal to the length of the shortest subsequence of the initial sequence of sorters still producing correct results for all possible data.

样例

Input
40 6
20 30
1 10
10 20
20 30
15 25
30 40
Output
4

5 人解决,9 人已尝试。

5 份提交通过,共有 16 份提交。

9.4 EMB 奖励。

创建: 7 年,8 月前.

修改: 1 年,5 月前.

最后提交: 10 月,3 周前.

来源: Central Europe 2003

题目标签