Minimizing maximizer#3059
The company Chris Ltd. is preparing a new device called Maximizer. Maximizer has inputs, numbered from to . Each input receives an integer. Maximizer has one output which represents the maximum value among its inputs.
Maximizer is implemented as a sequence of sorters Sorter(i_1, j_1), , Sorter(i_m, j_m). Each sorter has inputs and outputs. Sorter(, ) sorts the values on inputs , i + 1, , in non-decreasing order, while the other inputs are passed to the outputs unchanged. The output of the Maximizer is the -th output of its last sorter.
An intern (a former ACM participant) noticed that some sorters can be skipped and the Maximizer would still produce the correct result for all possible combinations of input values. Find the length of the shortest subsequence of sorters that still produces the correct result for all possible input data.
The input consists of several test cases. The first line of each test contains two integers and (2 \leq n \leq 50000, 1 \leq m \leq 500000), where is the number of inputs and is the number of sorters in the sequence. The initial sequence of sorters is described in the next lines. The -th line contains the parameters of the -th sorter: two integers i_k and j_k (1 \leq i_k < j_k \leq n).
For each test case, print on a separate line the length of the shortest subsequence of sorters which produces the same result as the initial sequence for all possible input data.
Esempio 1