CF1775D.Friendly Spiders

Mars is home to an unusual species of spiders — Binary spiders.

Right now, Martian scientists are observing a colony of $n$ spiders, the $i$-th of which has $a_i$ legs.

Some of the spiders are friends with each other. Namely, the $i$-th and $j$-th spiders are friends if $\gcd(a_i, a_j) \ne 1$, i. e., there is some integer $k \ge 2$ such that $a_i$ and $a_j$ are simultaneously divided by $k$ without a remainder. Here $\gcd(x, y)$ denotes the greatest common divisor (GCD) of integers $x$ and $y$.

Scientists have discovered that spiders can send messages. If two spiders are friends, then they can transmit a message directly in one second. Otherwise, the spider must pass the message to his friend, who in turn must pass the message to his friend, and so on until the message reaches the recipient.

Let's look at an example.

Suppose a spider with eight legs wants to send a message to a spider with $15$ legs. He can't do it directly, because $\gcd(8, 15) = 1$. But he can send a message through the spider with six legs because $\gcd(8, 6) = 2$ and $\gcd(6, 15) = 3$. Thus, the message will arrive in two seconds.

Right now, scientists are observing how the $s$-th spider wants to send a message to the $t$-th spider. The researchers have a hypothesis that spiders always transmit messages optimally. For this reason, scientists would need a program that could calculate the minimum time to send a message and also deduce one of the optimal routes.

火星上生活着一种奇特的蜘蛛——二进制蜘蛛。

目前，火星科学家正在观察一个由 $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$ 的最大公约数（GCD）。

科学家们发现，蜘蛛能够传递信息。若两只蜘蛛是朋友，则它们可在一秒钟内直接传输一条信息；否则，信息必须经由某只蜘蛛传递给它的朋友，该朋友再传递给它自己的朋友，依此类推，直至信息抵达接收者。

我们来看一个例子：

假设一只拥有 8 条腿的蜘蛛希望向一只拥有 15 条腿的蜘蛛发送信息。它无法直接发送，因为 $\gcd(8, 15) = 1$。但它可通过一只拥有 6 条腿的蜘蛛中转：由于 $\gcd(8, 6) = 2$ 且 $\gcd(6, 15) = 3$，因此信息可在两秒内送达。

目前，科学家正在观测第 $s$ 只蜘蛛向第 $t$ 只蜘蛛发送信息的过程。研究人员提出一个假说：蜘蛛总是以最优方式传递信息。因此，科学家需要一个程序，既能计算信息传递所需的最短时间，又能推导出一条最优路径。

The first line of input contains an integer $n$ ($2 \le n \le 3\cdot10^5$) — the number of spiders in the colony.

The second line of input contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 3\cdot10^5$) — the number of legs the spiders have.

The third line of input contains two integers $s$ and $t$ ($1 \le s, t \le n$) —the spiders between which the message must be sent.

输入的第一行包含一个整数 $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$）—— 需要传递消息的两只蜘蛛的编号。

If it is impossible to transmit a message between the given pair of spiders, print $-1$.

Otherwise, in the first line of the output print the integer $t$ ($t \ge 1$) — the number of spiders that participate in the message transmission (i. e. the minimum time of message delivery in seconds plus one). In the second line, print $t$ different integers $b_1, b_2, \ldots, b_t$ ($1 \le b_i \le n$) — the ids of the spiders through which the message should follow, in order from sender to receiver.

If there are several optimal routes for the message, output any of them.

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

否则，在输出的第一行打印整数 $t$（$t \ge 1$）——参与消息传输的蜘蛛数量（即消息送达所需的最短时间（秒）加一）。在第二行，打印 $t$ 个互不相同的整数 $b_1, b_2, \ldots, b_t$（$1 \le b_i \le n$）——消息应依次经过的蜘蛛编号，顺序为从发送者到接收者。

若存在多条最优传输路径，输出任意一条即可。

The first example is shown above. It shows that the message from the $5$-th spider (with eight legs) to the $6$-th spider (with $15$ legs) is optimal to pass through the $4$-th spider (with six legs).

In the second example, the spider number $7$ (with $11$ legs) is not friends with anyone, so it is impossible to send him a message.

第一个示例如上所示。它表明：从第 $5$ 只蜘蛛（有八条腿）向第 $6$ 只蜘蛛（有 $15$ 条腿）传递消息的最优路径是经过第 $4$ 只蜘蛛（有六条腿）。

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