CF1823B.Sort with Step

Let's define a permutation of length $n$ as an array $p$ of length $n$, which contains every number from $1$ to $n$ exactly once.

You are given a permutation $p_1, p_2, \dots, p_n$ and a number $k$. You need to sort this permutation in the ascending order. In order to do it, you can repeat the following operation any number of times (possibly, zero):

• pick two elements of the permutation $p_i$ and $p_j$ such that $|i - j| = k$, and swap them.

Unfortunately, some permutations can't be sorted with some fixed numbers $k$. For example, it's impossible to sort $[2, 4, 3, 1]$ with $k = 2$.

That's why, before starting the sorting, you can make at most one preliminary exchange:

• choose any pair $p_i$ and $p_j$ and swap them.

Your task is to:

1. check whether is it possible to sort the permutation without any preliminary exchanges,
2. if it's not, check, whether is it possible to sort the permutation using exactly one preliminary exchange.

For example, if $k = 2$ and permutation is $[2, 4, 3, 1]$, then you can make a preliminary exchange of $p_1$ and $p_4$, which will produce permutation $[1, 4, 3, 2]$, which is possible to sort with given $k$.

我们定义一个长度为 $n$ 的排列为一个长度为 $n$ 的数组 $p$，其中恰好包含从 $1$ 到 $n$ 的每个整数各一次。

给定一个排列 $p_1, p_2, \dots, p_n$ 和一个数 $k$。你需要将该排列按升序排序。为此，你可以重复执行以下操作任意次（包括零次）：

• 选取排列中的两个元素 $p_i$ 和 $p_j$，满足 $|i - j| = k$，并交换它们。

不幸的是，对某些固定的 $k$，部分排列无法被排序。例如，当 $k = 2$ 时，排列 $[2, 4, 3, 1]$ 无法被排序。

因此，在开始排序前，你最多可以进行一次预处理交换：

• 任选一对 $p_i$ 和 $p_j$ 并交换它们。

你的任务是：

1. 判断是否可以在不进行任何预处理交换的情况下将该排列排序；
2. 若不能，则判断是否可以通过恰好一次预处理交换使其可排序。

例如，若 $k = 2$ 且排列为 $[2, 4, 3, 1]$，则你可以预先交换 $p_1$ 和 $p_4$，得到排列 $[1, 4, 3, 2]$，而该排列在给定 $k$ 下是可以被排序的。

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

The first line of each test case contains two integers $n$ and $k$ ($2 \le n \le 2 \cdot 10^5$; $1 \le k \le n - 1$) — length of the permutation, and a distance between elements that can be swapped.

The second line of each test case contains $n$ integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$) — elements of the permutation $p$.

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

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

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$2 \le n \le 2 \cdot 10^5$；$1 \le k \le n - 1$）—— 分别表示排列的长度，以及可交换元素之间的距离。

每个测试用例的第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$（$1 \le p_i \le n$）—— 排列 $p$ 的元素。

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

For each test case print

• 0, if it is possible to sort the permutation without preliminary exchange;
• 1, if it is possible to sort the permutation with one preliminary exchange, but not possible without preliminary exchange;
• -1, if it is not possible to sort the permutation with at most one preliminary exchange.

对于每个测试用例，输出：

• 0，如果无需预先交换即可将该排列排序；
• 1，如果恰好需要一次预先交换才能将该排列排序，但无法在不进行预先交换的情况下完成排序；
• -1，如果即使最多进行一次预先交换，也无法将该排列排序。

In the first test case, there is no need in preliminary exchange, as it is possible to swap $(p_1, p_2)$ and then $(p_2, p_3)$.

In the second test case, there is no need in preliminary exchange, as it is possible to swap $(p_1, p_3)$ and then $(p_2, p_4)$.

In the third test case, you need to apply preliminary exchange to $(p_2, p_3)$. After that the permutation becomes $[3, 4, 1, 2]$ and can be sorted with $k = 2$.

在第一个测试用例中，无需预先交换，因为可以先交换 $(p_1, p_2)$，再交换 $(p_2, p_3)$。

在第二个测试用例中，无需预先交换，因为可以先交换 $(p_1, p_3)$，再交换 $(p_2, p_4)$。

在第三个测试用例中，需要对 $(p_2, p_3)$ 执行预先交换。此后排列变为 $[3, 4, 1, 2]$，并可在 $k = 2$ 的条件下完成排序。