AC代碼

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

題意：

火星上有一種不同尋常的蜘蛛——二元蜘蛛。

目前，火星科學(xué)家正在觀察一個由n只蜘蛛組成的群體，其中第i只蜘蛛有ai腿。

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

即，存在某個整數(shù)k≥2，使得ai和aj同時被k除而無余數(shù)。

科學(xué)家發(fā)現(xiàn)蜘蛛可以發(fā)送信息。如果兩個蜘蛛是朋友，那么它們可以在一秒鐘內(nèi)直接發(fā)送信息。否則，蜘蛛必須將消息傳遞給他的朋友，而朋友又必須將消息傳給他的朋友。

依此類推，直到消息到達接收者。

讓我們看一個例子。

假設(shè)一只8條腿的蜘蛛想要向一只15條腿的蜘蛛發(fā)送信息。

他不能直接做，因為gcd（8，15）=1。但他可以用六條腿通過蜘蛛發(fā)送信息，

因為gcd（8，6）=2，gcd（6，15）=3。因此，消息將在兩秒內(nèi)到達。

現(xiàn)在，科學(xué)家們正在觀察第s只蜘蛛是如何向第t只蜘蛛發(fā)送信息的。

研究人員假設(shè)蜘蛛總是以最佳方式傳遞信息。因此，科學(xué)家需要一個程序來計算發(fā)送消息的最短時間，

并推斷出最佳路線之一。

題解：

數(shù)論 + BFS