G. DSU
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Since her creation to maintain the Tethys system, the Shorekeeper has diligently studied various algorithms under her creator's guidance. Among these, she found the Disjoint Set Union (DSU) data structure to be the most elegant. Her implementation uses the following code:

vector<int> f(n); iota(f.begin(), f.end(), 0); // initialize f[i] = i

int find(int u){ return f[u] == u ? u : f[u] = find(f[u]); } // path compression

void merge(int u, int v){ u = find(u); v = find(v); f[u] = v; }

Your task is to determine whether a given array $$$f$$$ could result from applying at most $$$n$$$ merge operations on an initially created DSU structure. The initial state uses the first code snippet above, and subsequent operations may only call the merge function.

Input

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

The first line of each test case contains one integer $$$n$$$ ($$$1\le n\le 4\cdot 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$f_0,f_1,\dots,f_{n-1}$$$ ($$$0\le f_i \lt n$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$4\cdot 10^5$$$.

Output

For each test case, if a solution exists, output as follows:

  • The first line contains one integer $$$k$$$ ($$$0\le k\le n$$$) — the number of merge calls.
  • The following $$$k$$$ lines each contain two integers $$$u$$$ and $$$v$$$ ($$$0\le u,v \lt n$$$), indicating calling merge(u, v).

; otherwise, output $$$-1$$$ in a single line.

Example
Input
3
1
0
2
1 0
3
0 1 0
Output
0
-1
1
2 0