核心思想

使用反向 BFS + 贪心选择的方法：

从终点 n 出发，反向标记所有能到达终点的点

从起点 1 出发，按照字典序优先选择 'a'

检测是否进入无法到达终点的环

算法步骤

构建反向图并标记可达点

对于每个位置 i，如果 i + aᵢ 在 [1, n] 范围内，则建立反向边

如果 i + bᵢ 在 [1, n] 范围内，也建立反向边

从终点 n 开始 BFS，标记所有能到达 n 的点

贪心构造路径

从起点 1 开始，优先尝试选择 'a'

如果选择 'a' 能到达已标记的点，则选择 'a'

否则尝试选择 'b'

如果两种选择都不可行，则无解

环检测

在构造路径时，如果访问到已经访问过的点，说明存在环

如果环中的点都能到达终点，则路径有限

如果环中有不能到达终点的点，则输出 "Infinity!"

复杂度分析

时间复杂度：O(n)

构建反向图：O(n)

反向 BFS：O(n)

贪心构造路径：O(n)

空间复杂度：O(n)

存储图结构：O(n)

标记数组：O(n)

关键点说明

反向 BFS：从终点出发标记可达点，避免在正向前进时走入死胡同

字典序贪心：在每一步优先选择 'a'，保证字典序最小

环检测：通过 visited 数组检测是否进入循环，结合可达性判断输出 "Infinity!"