Вам даны два целых числа $$$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$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$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$$$ пар вершин кратчайшее расстояние между ними.
25 41 21 31 41 58 33 72 51 7
1221123
Так выглядит граф для первого набора входных данных:
Так выглядит граф для второго набора входных данных:
| Codeforces Round 1099 (Div. 2) |
|---|
| Закончено |
