← 返回题目列表

Codeforces · 2231/F

F. 二次跳跃

中文机器翻译题面 查看原题

给你两个整数 $$$n$$$ 和 $$$q$$$。考虑一个具有 $$$n$$$ 个顶点的图,其中顶点 $$$i$$$ 和 $$$j$$$ 通过边连接当且仅当 $$$|j - i|$$$ 是完美正方形$$$^{\text{*}}$$$。

给你 $$$q$$$ 数字对 $$$a_i, b_i$$$。对于每个 $$$q$$$ 对,您需要找到该图中顶点 $$$a_i$$$ 和 $$$b_i$$$ 之间的最短距离。可以证明图是连通的,所以$$$a_i$$$和$$$b_i$$$之间的距离不是无限的。

$$$^{\text{*}}$$$如果存在整数 $$$y$$$ 使得 $$$x = y^2$$$,则整数 $$$x$$$ 是完全平方数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$。

输出

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

示例

输入
复制

2
5 4
1 2
1 3
1 4
1 5
8 3
3 7
2 5
1 7

输出
复制

1
2
2
1
1
2
3

注意

第一个测试用例的图表如下所示:

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