题解

问题核心：
给定每个国家 i 的护照可访问区间 [Li, Ri]。从起点 s 出发，每次可获取当前所在国的护照（获得访问区间），再凭已有护照走到其他国家。问能否访问所有国家，以及最少需要获取多少本护照。

关键建模：
将国家视为点。一本护照相当于从签发国 i 向其可访问区间 [Li, Ri] 内的所有点连有向边（即 i → j 对 Li ≤ j ≤ Ri）。这样问题转化为在有向图中，从 s 出发经过若干次“边权为 1”的扩展（获得护照），最终到达所有点的最小代价。

解决思路：

1. 连通性判断：
   先建图并缩点（强连通分量 SCC），判断 s 所在的 SCC 是否能到达所有其他 SCC（或者所有 SCC 在缩点后的 DAG 上是一条链且 s 在链的一端），否则答案为 -1。

2. 最小护照数：
   问题转化为：在缩点后的 DAG 上，需要选择尽可能少的节点（对应获得相应国家的护照），使得从 s 出发可以到达所有节点。
   这等价于求 DAG 上从 s 出发的“最小路径覆盖”或“最小前驱集”。可以用 BFS/DP 处理，每个护照的可访问区间相当于覆盖一段连续的 SCC（因为护照区间连续）。

3. 优化：
   由于护照区间是连续的，缩点后的 SCC 在编号上也是连续的。可以预处理每个 SCC 的“可达范围”（最左/最右可达 SCC 编号），转化为区间覆盖问题：
   从 s 所在 SCC 开始，每次选择当前已覆盖区间内的一个 SCC（代表获得该国的护照），用其护照扩展覆盖范围，直到覆盖所有 SCC。贪心选择扩展范围最大的即可（用优先队列或线段树维护）。

时间复杂度：
O(N log N) 或 O(N) 可处理 N = 2×10^5。

实现细节：

• 用 Tarjan 算法求 SCC。
• 用区间并查集或线段树维护当前已覆盖区间和可达范围。
• 多组起点预处理每个 SCC 的扩展信息（向外最左/最右可达 SCC），避免重复计算。