C. Shortest Cycle
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two integers, $$$n$$$ and $$$m$$$. Using these, we define two infinite, 1-indexed sequences, $$$A$$$ and $$$B$$$:

  • Sequence $$$A$$$ is the repeating sequence $$$[1, 2, \dots, n, 1, 2, \dots, n, \dots]$$$.
  • Sequence $$$B$$$ is the repeating sequence $$$[n + 1, n + 2, \dots, n + m, n + 1, n + 2, \dots, n + m, \dots]$$$.
This means for any index $$$i \ge 1$$$, $$$A_i = ((i-1) \pmod n) + 1$$$ and $$$B_i = ((i-1) \pmod m) + n + 1$$$.

Now, construct a graph with $$$n + m$$$ nodes. In this graph, there exists an undirected edge connecting node $$$u$$$ and node $$$v$$$ if and only if there exists some index $$$i \ge 1$$$ such that $$$A_i = u$$$ and $$$B_i = v$$$.

Note: a cycle is a path in a graph that starts and ends at the same vertex, with no repeated edges and at least one edge.

Your task is to find the smallest cycle in the resulting graph. If there are multiple cycles of the same smallest size, you may print any one of them. If the graph is acyclic, print -1.

Input

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 $$$m$$$ $$$(2 \le n, m \le 10^5)$$$.

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

Output

For each test case, if the graph is acyclic print -1. Otherwise, in the first line print a single integer k $$$(3 \le k \le n + m)$$$ — the size of the smallest cycle in the graph. In the next line print k distinct integers $$$(c_1, c_2, ..., c_k)$$$, describing the cycle. for $$$1 \lt i \le k$$$ the node $$$c_i$$$ should be connected to the node $$$c_{i - 1}$$$. and node $$$c_k$$$ should be connected to node $$$c_1$$$.

It is guaranteed that the sum of $$$k$$$ over all test cases does not exceed $$$10^6$$$.

Example
Input
3
2 3
2 4
4 6
Output
4
1 5 2 3
-1
4
5 3 7 1
Note

Explanation of the example:

The first test case:

A = $$$[1, 2, 1, 2, 1, 2, ...]$$$

B = $$$[3, 4, 5, 3, 4, 5, ...]$$$

The second test case:

A = $$$[1, 2, 1, 2, 1, 2, ...]$$$

B = $$$[3, 4, 5, 6, 3, 4, ...]$$$

For the first test case, the following cycles (of size 4) are also accepted:

$$$[1, 4, 2, 5]$$$

$$$[3, 2, 4, 1]$$$

the graph for the first test casethe graph for the second test case