25254번 - Joined Sessions 다국어

Lucy is very lazy. Her boss asked her to go to a conference and of course she wants her to go to as many meetings as possible. But Lucy is lazy and so she decides to choose her meetings such that all other meetings overlap with at least one of the meetings she is attending. This way, her boss cannot complain as there is no way for her to attend additional meetings.

While reading the schedule of the conference, Lucy finds out that even with this approach of choosing the meetings there are quite many meetings she has to attend. Luckily, her good friend Max is one of the organisers of the conference and in particular responsible for the timetable. Max is unfortunately not able to cancel meetings or to reschedule them, but he can help Lucy in another way.

Since the meetings are normally boring, nobody will pay too much attention if the topic changes. Therefore, whenever there are two meetings that overlap, he can combine them into a single meeting instead. Two meetings $a$ and $b$ overlap if $\text{start}(a) \le \text{start}(b) \le \text{end}(a)$ or vice versa, and when they are combined the new meeting will start at time $\min(\text{start}(a),\text{start}(b))$ and end at time $\max(\text{end}(a),\text{end}(b))$. Max can then repeat this merging process and it is even possible to further combine these combined meetings with other meetings. Non-overlapping meetings cannot be combined as then people would notice that someone is tampering with the schedule.

Lucy now wonders if she can reduce the number of meetings she has to attend with this method. If it is possible, how many such merges are necessary to reduce this number by at least one?

The input consists of:

• One line with an integer $n$ ($2 \leq n \leq 10^6$), the number of meetings.
• $n$ lines describing the meetings, each with two integers $a$ and $b$ ($0 \leq a \leq b \leq 10^9$), where $a$ is the start time and $b$ the end time of one of the given meetings.

If it is possible to reduce the number of meetings Lucy has to attend, then output the minimum number of merging operations needed to do so. Otherwise output impossible.