AT_pakencamp_2024_day1_d Coprime Shortest Path

有一个包含 $N$ 个顶点的无向图，顶点编号为 $1, 2, \ldots, N$。 对于所有整数 $u, v$ 满足 $1 \leq u < v \leq N$，若 $u$ 与 $v$ 互质，则在顶点 $u$ 和顶点 $v$ 之间连一条边，除此之外没有其他边。 请你求出，从顶点 $S$ 到顶点 $T$ 至少需要经过多少条边。

输入从标准输入中读入，格式如下： > $N$ $S$ $T$

输出答案。

### 样例解释 1 该图如下所示。  如果从 $2 \to 3 \to 4$ 走，那么经过的边数是 $2$。由于无法在 $1$ 步内到达，因此输出 $2$。 ### 样例解释 2 注意，输入数据可能超出 32 位整数范围。 ### 数据范围 - $2 \leq N \leq 10^{18}$ - $1 \leq S, T \leq N$ - $S \neq T$ - 所有输入均为整数。 由 ChatGPT 5 翻译