Ir al contenido (saltar navegación)

El alienígena infiltrado

Tiempo máximo: 2,000-3,000 sMemoria máxima: 8192 KiB
Radiotelescopio

Eres un alienígena espía preocupado porque los radiotelescopios terrestres pueden descubrir tu planeta. Después de décadas de trabajo encubierto como estudiante de Físicas, te has convertido en el encargado de planificar los trabajos en el radiotelescopio más importante de la Tierra.

Tu planeta será particularmente susceptible de ser encontrado durante el intervalo [C, F). Durante ese tiempo, se han propuesto una serie de trabajos de investigación, donde cada uno, de ser aprobado, utilizará el radiotelescopio en un intervalo [ci, fi). Los intervalos no pueden alargarse o acortarse, pero pueden solapar, es decir, el radiotelescopio puede estar dando servicio simultáneamente a varios trabajos.

Tu objetivo es minimizar las posibilidades de que tu planeta sea descubierto, teniendo en cuenta que cuantos más trabajos se lleven a cabo mayor será la posibilidad de que lo descubran. Por otra parte, debes evitar que la planificación resulte sospechosa ya que podrían desenmascararte. Para ello, la planificación debe cubrir todo el intervalo [C, F) de forma que el radiotelescopio esté dando servicio a al menos un trabajo en cada momento.

Entrada

La entrada consta de una serie de casos de prueba. Cada uno comienza con una línea con tres enteros: C y F, con C < F, que representan el comienzo y la finalización del intervalo en el que tu planeta estará expuesto; y N, que representa el número de trabajos de investigación propuestos (0 ≤ N ≤ 200.000). A continuación aparecerán N líneas cada una con dos enteros [ci, fi), con ci < fi, representando el comienzo y la finalización del intervalo en que cada uno de los trabajos utilizaría el telescopio. Todos los extremos de intervalos son valores entre 0 y 109. La entrada terminará con la línea 0 0 0.

Salida

Para cada caso de prueba se escribirá una línea con el mínimo número de trabajos que es necesario seleccionar para cubrir todo el intervalo [C, F). Si no es posible cubrir el intervalo se escribirá Imposible.

Entrada de ejemplo

1 10 4
2 8
0 5
7 11
5 10
0 3 2
0 1
2 3
0 0 0

Salida de ejemplo

2
Imposible