The supermarket decided to broadcast advertisements for new products from time to time. In order to create the optimal schedule for broadcasting advertising, the supermarket management conducted the following study: during the day, for each customer who visited the supermarket, the time when he arrived at the supermarket and when he left it was recorded.
The advertising manager assumed that such a schedule of arrivals and departures of buyers would continue in the following days. He wants to schedule commercials so that each customer hears at least two advertisements. At the same time, he stipulated that two advertisements should not be broadcast at the same time and, since the sellers had to listen to these advertisements all the time, the total number of advertisements per day was minimal.
Write a program that will create such a schedule for broadcasting commercials. Advertisements can start broadcasting only at whole points in time. Each advertisement is considered to end before the next integer point in time. If an advertisement is broadcast at the moment when the customer enters or leaves the supermarket, the customer has time to hear this advertisement.
Input
The input file contains first the number N — number of shoppers visiting the supermarket per day (1<N<3000). Then comes N pairs of natural numbers Ai, Bi, specifying the time of arrival and departure of customers from the supermarket, respectively (0<A
i<B
i<106).
Imprint
In the output file, first print the number of advertisements that will be broadcast per day. Then output in ascending order the time points at which you want to broadcast advertisements.
If there are several solutions, print any of them.
Examples
| # |
Input |
Output |
| 1 |
5
1 10
10 12
1 10
1 10
23 24 |
5
5 10 12 23 24
|