> 有向环上 $a \to b$ 经过的最小边数被定义为单词 $a$ 和单词 $b$ 之间的语义偏差度 —— **由于翻译家并不像 OI 选手那样具备逆向思维**，因此单词 $a$ 和单词 $b$ 之间的语义偏差度不一定等于单词 $b$ 和单词 $a$ 之间的语义偏差度。

考虑逆向思维，从单词 $i$ 沿着与题目描述相反的方向回译到单词 $i$。

（在下面的讨论中，我们默认单词 $i$ 可以翻译到单词 $i$ 本身，因为这显然不影响答案 —— 这只会增加翻译次数，而不能推进翻译进度，没人愿意这么做。）

于是我们惊喜地发现：

- 单词 $i$ 反向翻译一次能翻译到的单词恰好在环上构成一个半开半闭区间，其中闭区间的端点是单词 $i$ 本身，开区间的端点是距离单词 $i$ 反向距离最近的同语言单词 $j$。
- 在此基础上，如果我们再进行一次反向翻译，那么能翻译到的单词是所有「上一次能翻译到的单词」这次能翻译到的单词的并集。因为所有区间都是闭区间点为本身的半开半闭区间，所以这些区间的并集仍然是半开半闭区间，其中开区间的端点是所有「子区间内开区间的端点」中距离单词 $i$ 反向最远的单词。
- 随着翻译次数的增加，当这个反向最远的单词从单词 $i$ 开始绕着环反向跑了一圈又穿过单词 $i$ 来到它后面时，我们就求出了回译单词 $i$ 所需的最小翻译次数 —— 它就是使得这一事件发生所需的最小翻译次数。

直接二分每个答案并用 ST 表和（不属于 ST 表的）倍增实现对那个反向最远的单词的高效查询即可。

最终的时间复杂度为 $O(Tn \log^2 n)$，空间复杂度为 $O(n \log^2 n)$，瓶颈均在预处理部分。

（实际上，我们也可以套用 $O(n)-O(1)$ RMQ 把时间复杂度降到 $O(Tn \log n)$，空间复杂度降到 $O(n \log n)$，但是意义不大。）