There are $n$ cats active in a certain region, each with its own habitat, numbered from $1$ to $n$. There are $m$ roads connecting these habitats, with the total number of roads not exceeding $2n - 4$. The $i$-th road connects habitat $a_i$ and habitat $b_i$. Cats can move bidirectionally between habitats along these roads, and no two different roads connect the same pair of habitats. Three animal protection groups are to take over this region. Please assist in assigning these $n$ habitats to the 3 groups, satisfying the following requirements:

• Each habitat is managed by exactly 1 group, and each group must manage at least 1 habitat. The habitats belonging to each group do not necessarily have to be connected.
• For ease of management, each group will remove the roads between the habitats it is responsible for. In other words, if a road connects two habitats that are assigned to the same group, that road will be removed.
• After these roads are removed, the remaining roads must not form a "cycle," to prevent cats from running around in circles, which would make them difficult for staff to catch. That is, there cannot exist a sequence of distinct habitats $v_1, v_2, \dots, v_k$ such that $k \ge 3$, and for all $1 \le i < k$, there is an unremoved road connecting habitat $v_i$ and habitat $v_{i+1}$, and there is also an unremoved road connecting $v_k$ and $v_1$.

For example, if there are 5 habitats and the road connections are as shown in the figure below:

We can assign habitats 3, 4, and 5 to the first group, habitat 1 to the second group, and habitat 2 to the third group. After removing the roads, the configuration is as shown below:

The remaining roads do not contain any cycles, so this is a valid assignment that meets the goal.

Please output which habitats each of the 3 groups should manage. If there are multiple ways to satisfy the conditions, output any one of them.

Input

The input contains multiple test cases.

t
test_1
test_2
...
test_t

• $t$ represents the number of test cases.
• $test_i$ is the $i$-th test case.

The input format for each test case is as follows:

n m
a_1 b_1
a_2 b_2
...
a_m b_m

• $n$ is the number of cat habitats.
• $m$ is the number of roads.
• $a_i, b_i$ are the habitat numbers connected by the $i$-th road. No two different roads connect the same pair of habitats.

Output

Output the answers for $t$ test cases.

answer_1
answer_2
...
answer_t

• $answer_i$ is the answer for the $i$-th test case.

The output format for the answer of each test case is as follows:

k_1 c_{1,1} ... c_{1,k_1}
k_2 c_{2,1} ... c_{2,k_2}
k_3 c_{3,1} ... c_{3,k_3}

• $k_i$ is the total number of habitats assigned to the $i$-th group.
• $c_{i,j}$ is the $j$-th habitat assigned to the $i$-th group.

If no such assignment exists for a test case, output -1.

-1

Constraints

• $1 \le t \le 3 \times 10^5$.
• $3 \le n \le 3 \times 10^5$.
• $0 \le m \le 2n - 4$.
• $1 \le a_i, b_i \le n$, $a_i \neq b_i$.
• The sum of $n$ over all test cases does not exceed $3 \times 10^5$.

Examples

Input 1

1
5 6
1 2
2 3
3 4
4 5
5 3
4 2

Output 1

3 3 4 5
1 1
1 2

Input 2

2
5 4
1 2
1 3
3 4
3 5
5 4
1 2
2 3
1 3
4 5

Output 2

2 1 2
1 3
2 4 5
3 1 2 3
1 4
1 5

Subtasks