CF2231F.Quadratic Jumps

You are given two integers $n$ and $q$. Consider a graph with $n$ vertices, where vertices $i$ and $j$ are connected by an edge if and only if $|j - i|$ is a perfect square$^{\text{∗}}$.

You are given $q$ pairs of numbers $a_i, b_i$. For each of these $q$ pairs, you need to find the shortest distance between vertices $a_i$ and $b_i$ in this graph. It can be proved that the graph is connected, so the distance between $a_i$ and $b_i$ is not infinite.

$^{\text{∗}}$An integer $x$ is a perfect square if there exists an integer $y$ such that $x = y^2$.

给你两个整数 $n$ 和 $q$。考虑一个包含 $n$ 个顶点的图，其中顶点 $i$ 与顶点 $j$ 之间存在一条边，当且仅当 $|j - i|$ 是一个完全平方数$^{\text{∗}}$。

你将得到 $q$ 对数字 $a_i, b_i$。对于这 $q$ 对中的每一对，你需要求出该图中顶点 $a_i$ 与 $b_i$ 之间的最短距离。可以证明该图是连通的，因此 $a_i$ 与 $b_i$ 之间的距离是有限的。

$^{\text{∗}}$ 整数 $x$ 是一个完全平方数，当且仅当存在整数 $y$，使得 $x = y^2$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $q$ ($2 \le n \le 2 \cdot 10^5$, $1 \le q \le 10^5$) — the number of vertices in the graph and the number of pairs of vertices for which the distance must be found.

Then the next $q$ lines describe the pairs of vertices for which the shortest distance must be found. Each pair is described by two numbers $a, b$ ($1 \leq a \lt b \leq n$) — the numbers of the vertices between which the shortest distance must be found.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$, and the sum of $q$ over all test cases does not exceed $10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 1000$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $q$（$2 \le n \le 2 \cdot 10^5$，$1 \le q \le 10^5$）—— 分别表示图中顶点的数量以及需要查询最短距离的顶点对数量。

接下来的 $q$ 行描述需要查询最短距离的顶点对。每一对由两个数字 $a, b$（$1 \leq a \lt b \leq n$）描述——即需要查询最短距离的两个顶点的编号。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$，且所有测试用例的 $q$ 之和不超过 $10^5$。

For each test case, output the shortest distance between each of the $q$ pairs of vertices.

对于每个测试用例，输出 $q$ 对顶点之间各自的最短距离。

This is what the graph looks like for the first test case:

• For the first pair of vertices, the shortest path is $1 \rightarrow 2$.
• For the second pair of vertices, the shortest path is $1 \rightarrow 2 \rightarrow 3$.
• For the third pair of vertices, the shortest path is $1 \rightarrow 5 \rightarrow 4$.
• For the fourth pair of vertices, the shortest path is $1 \rightarrow 5$.

This is what the graph looks like for the second test case:

• For the first pair of vertices, the shortest path is $1 \rightarrow 2$.
• For the second pair of vertices, the shortest path is $2 \rightarrow 6 \rightarrow 5$.
• For the third pair of vertices, the shortest path is $1 \rightarrow 2 \rightarrow 6 \rightarrow 7$.

第一个测试用例对应的图如下所示：

• 对于第一对顶点，最短路径为 $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$。