P6902 [ICPC 2014 WF] Surveillance

题目描述

给定一个长度为 $n$ 的环，有 $k$ 个区域被覆盖，求最小的满足环被完全覆盖的区域数量。

输入格式

第一行两个整数 $n,k$。 接下来 $k$ 行，每行两个整数表示一个区域。

输出格式

若环不可能被完全覆盖，输出 impossible；否则输出一个整数，表示最少的区域数量。

输入输出样例 #1

输入 #1

100 7
1 50
50 70
70 90
90 40
20 60
60 80
80 20

输出 #1

3

输入输出样例 #2

输入 #2

8 2
8 3
5 7

输出 #2

impossible

输入输出样例 #3

输入 #3

8 2
8 4
5 7

输出 #3

2

说明/提示

$3\leq n\leq 10^6,1\leq k\leq 10^6.$