U232146 [sxyz NOIP 模拟赛] 2 环覆盖（ring）

[sxyz NOIP 模拟赛]2 环覆盖（ring）T2 ------------ 3s 512MB

一个环上按照顺序分布着点 1, 2, ..., n 给定 m 个区间，第 i 个区间覆盖 [li, ri] 范围内的所有整点，特别的，若 li > ri，其覆盖范围为 [li, n] ∪ [1, ri] 你需要从中选出最少的区间，覆盖所有 n 个点，并输出这个区间数。特别的，如果无法覆盖，则输出 impossible

第一行两个整数 n, m 接下来 m 行，每行两个整数，表示一个区间

一行一个整数，表示答案

2.4 数据范围与提示 对于 30% 的数据，li ≤ ri 对于另 40% 的数据，n, m ≤ 5000 对于所有数据，n, m ≤ 10$^6$, 1 ≤ li, ri ≤ n ------------ 因为某些原因，本题无法上传大样例。