Minimum Water Stations

You are given a set of water station intervals along a straight path, where each interval represents the range (in meters) that a water station can cover. The path starts at meter 1 and ends at meter 100,000. Your task is to determine the minimum number of water stations needed to cover the entire path. If it is impossible to cover the path with the given intervals, output IMPOSSIBLE.

Note: The intervals may overlap, and you must choose the minimal set of intervals such that combined they cover the whole range from 1 to 100,000. You are encouraged to use a greedy algorithm to solve this problem efficiently.

The problem can be mathematically modeled as covering the interval \([1, 100000]\) with a set of intervals \([a_i, b_i]\). At each step, select the interval that covers the maximum range starting from the current uncovered point. If no such interval exists, the answer is \(IMPOSSIBLE\).

inputFormat

The first line contains a single integer N representing the number of water station intervals. Each of the following N lines contains two space-separated integers a and b indicating that the water station covers the interval from a to b (inclusive).

outputFormat

Output a single line. If it is possible to cover the entire path from 1 to 100,000, output the minimum number of water stations required. Otherwise, output IMPOSSIBLE.

3
1 30000
25000 70000
65000 100000

3