CF2231F Quadratic Jumps

给定两个整数 $n$ 和 $q$。考虑一个有 $n$ 个顶点的图，当且仅当 $|j - i|$ 是一个完全平方数$^{\text{∗}}$时，顶点 $i$ 和 $j$ 之间有一条边。 给定 $q$ 对数字 $a_i, b_i$。对于每一对，需要你在上述图中找出顶点 $a_i$ 和 $b_i$ 之间的最短距离。可以证明，该图是连通的，因此 $a_i$ 和 $b_i$ 之间的距离一定不是无穷大。 $^{\text{∗}}$ 若存在整数 $y$ 使得 $x = y^2$，则整数 $x$ 是完全平方数。

每组测试数据包含多组测试用例。第一行为测试用例数 $t$（$1 \leq t \leq 1000$）。接下来为每组测试用例的描述。 每组测试用例的第一行为两个整数 $n$ 和 $q$（$2 \leq n \leq 2 \cdot 10^5，1 \leq q \leq 10^5$），分别表示图中的顶点数和需查询最短距离的顶点对数。 接下来的 $q$ 行每行包含两个整数 $a, b$（$1 \leq a < b \leq n$），表示需查询最短距离的两个顶点。 保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$，所有测试用例的 $q$ 之和不超过 $10^5$。

对于每组测试用例，依次输出对于每一对顶点的最短距离。

这是第一组测试用例的图示：  - 对于第一对顶点，最短路径为 $1 \rightarrow 2$。 - 对于第二对顶点，最短路径为 $1 \rightarrow 2 \rightarrow 3$。 - 对于第三对顶点，最短路径为 $1 \rightarrow 5 \rightarrow 4$。 - 对于第四对顶点，最短路径为 $1 \rightarrow 5$。 这是第二组测试用例的图示：  - 对于第一对顶点，最短路径为 $1 \rightarrow 2$。 - 对于第二对顶点，最短路径为 $2 \rightarrow 6 \rightarrow 5$。 - 对于第三对顶点，最短路径为 $1 \rightarrow 2 \rightarrow 6 \rightarrow 7$。 由 ChatGPT 5 翻译