AC代码

https://codeforces.com/contest/1775/submission/190458498

题意：

火星上有一种不同寻常的蜘蛛——二元蜘蛛。

目前，火星科学家正在观察一个由n只蜘蛛组成的群体，其中第i只蜘蛛有ai腿。

【资料图】

有些蜘蛛彼此是朋友。也就是说，如果gcd（ai，aj）≠1，则第i个和第j个蜘蛛是朋友，

即，存在某个整数k≥2，使得ai和aj同时被k除而无余数。

科学家发现蜘蛛可以发送信息。如果两个蜘蛛是朋友，那么它们可以在一秒钟内直接发送信息。否则，蜘蛛必须将消息传递给他的朋友，而朋友又必须将消息传给他的朋友。

依此类推，直到消息到达接收者。

让我们看一个例子。

假设一只8条腿的蜘蛛想要向一只15条腿的蜘蛛发送信息。

他不能直接做，因为gcd（8，15）=1。但他可以用六条腿通过蜘蛛发送信息，

因为gcd（8，6）=2，gcd（6，15）=3。因此，消息将在两秒内到达。

现在，科学家们正在观察第s只蜘蛛是如何向第t只蜘蛛发送信息的。

研究人员假设蜘蛛总是以最佳方式传递信息。因此，科学家需要一个程序来计算发送消息的最短时间，

并推断出最佳路线之一。

题解：

数论 + BFS