CF1775D Friendly Spiders

题目描述

火星上有一种奇特的蜘蛛——二进制蜘蛛。

现在，火星科学家正在观察一个由 $n$ 只蜘蛛组成的群落，第 $i$ 只蜘蛛有 $a_i$ 条腿。

有些蜘蛛彼此是朋友。具体来说，如果第 $i$ 只和第 $j$ 只蜘蛛满足 $\gcd(a_i, a_j) \ne 1$，即存在某个整数 $k \ge 2$，使得 $a_i$ 和 $a_j$ 都能被 $k$ 整除，则这两只蜘蛛是朋友。这里 $\gcd(x, y)$ 表示整数 $x$ 和 $y$ 的最大公约数。

科学家们发现蜘蛛可以传递消息。如果两只蜘蛛是朋友，它们可以在一秒内直接传递消息。否则，蜘蛛必须把消息传递给它的朋友，再由朋友传递给朋友，依此类推，直到消息到达接收者。

让我们来看一个例子。

假设一只拥有八条腿的蜘蛛想要向一只拥有 $15$ 条腿的蜘蛛发送消息。它不能直接发送，因为 $\gcd(8, 15) = 1$。但它可以通过一只拥有六条腿的蜘蛛传递消息，因为 $\gcd(8, 6) = 2$ 且 $\gcd(6, 15) = 3$。因此，消息将在两秒内到达。

目前，科学家们希望找到第 s 个蜘蛛向第 t 个蜘蛛发送消息的最短时间。

输入的第一行包含一个整数 $n$（$2 \le n \le 3\cdot10^5$），表示蜘蛛群落中的蜘蛛数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 3\cdot10^5$），表示每只蜘蛛拥有的腿数。

第三行包含两个整数 $s$ 和 $t$（$1 \le s, t \le n$），表示需要传递消息的两只蜘蛛的编号。

如果无法在给定的两只蜘蛛之间传递消息，输出 $-1$。

否则，在第一行输出最短时间（单位：秒）。在第二行，输出最短路径，也就是经过传递信息的蜘蛛在 a 数组的位置。按照从发送者到接收者的顺序排列，如果有多个最佳路径，输出字典序最小的一个。

第一个样例如上图所示。它展示了从第 $5$ 只蜘蛛（有八条腿）到第 $6$ 只蜘蛛（有 $15$ 条腿）最优的传递路径是经过第 $4$ 只蜘蛛（有六条腿）。

在第二个样例中，第 $7$ 只蜘蛛（有 $11$ 条腿）与任何蜘蛛都不是朋友，因此无法向它发送消息。