405594: GYM102006 G Is Topo Logical?

G. Is Topo Logical?time limit per test2.5 secondsmemory limit per test256 megabytesinputtopo.inoutputstandard output

A topologicial sort of a directed graph is a linear ordering of its vertices such that for every directed edge going from u into v in the graph, u comes before v in the ordering. A commonly used example is a graph of courses, where the directed edge represents that the course u must be taken before the course v. Hence making its topological sort a possible ordering of taking courses.

Mr. Topo has a directed graph. He calculated the in-degree for each node, which is equal to the number of edges going into the node, then he ran the following algorithm to obtain a topological ordering:

1. Find a node u with zero in-degree that was not processed before.
2. If no such u is found, terminate the algorithm.
3. Otherwise, subtract 1 from the in-degree of v for all nodes v where is a directed edge in the graph. Repeat at step 1.

You will be given the initial in-degrees before running the algorithm, and the final in-degrees after the algorithm is terminated. Find a directed graph which would produce the given in-degree values before and after running the algorithm.

Your only conditions are that the graph must not contain self-loops nor repeated edges. A self-loop is an edge from the node to itself . Note that edge is different from .

Input

The first of input contains a single integer T (1 ≤ T ≤ 370), the number of test cases.

The first line of each test case contains a single the integer n (1 ≤ n ≤ 2 × 10⁵), the number of nodes in the graph.

The second line contains n space-separated integers a₁, a₂, ..., a_n (0 ≤ a_i < n), where a_i is the initial in-degree of node i.

The third line contains n space-separated integers b₁, b₂, ..., b_n (0 ≤ b_i ≤ a_i), where b_i is the final in-degree of node i.

It is gauranteed that , for each test case.

The sum of n over all test cases doesn't exceed 2 × 10⁶.

The sum of all a_i values over all test cases doesn't exceed 2 × 10⁶.

Output

For each test case, if there is no valid graph, output only  - 1 on a single line. Otherwise, output the number of edges m on the first line, and list the m directed edges (1 ≤ u, v ≤ n) of the graph in the following m lines.

If there is more than one valid solution, output any of them.

ExampleInput

3
5
0 1 1 1 1
0 1 1 1 1
3
0 1 0
0 1 0
5
0 2 1 1 3
0 1 1 1 2

Output

4
3 2
2 3
2 4
2 5
-1
7
3 2
2 3
1 2
2 4
1 5
2 5
3 5