New Sky

This is an Output only problem, meaning you only need to submit the output file, not the code. When submitting, please use the "Plain Text" compiler. You can find the input test at this link: https://static.e-olymp.com/problems/10457/input.txt.

Colonizing Mars is old news. We need to think further ahead. For instance, what challenges will colonizers face beyond our galaxy? A new planet, new continents, a new starry sky.

While we can manage the colonization of continents—claiming an area, naming it New New England, and building a New New Orleans—navigating the starry sky is more complex. Humanity has always lived under one sky, or two if you consider the hemispheres. But how do we navigate an alien sky? Where is the Little Bear, where is the Southern Cross, and are they even there? No one knows.

Thus, we will search for familiar constellations in the new sky.

Imagine the starry sky as an undirected graph. Stars are vertices, and imaginary lines that can form constellations are edges. Known constellations are also represented as such graphs. We provide a list of constellations and a map of the sky, and your task is to find these constellations on the map.

Each star and imaginary line in the sky can belong to only one constellation. Not all constellations we seek are present on the celestial sphere, as it is another galaxy. However, some may appear multiple times, and in such cases, finding the first occurrence is sufficient.

The number of points scored in each test corresponds to the number of successfully found constellations.

Input

The first line contains a single integer T, the number of tests.

The first line of each test contains a single integer K. This is followed by K+1 blocks, where the first K blocks describe the sought constellations, and the last block describes the entire sky map.

Each block consists of two lines. The first line contains two integers: $N_i$, the number of stars in the group, and $M_i$, the total number of connections between the stars in the current group. The second line contains $M_i$ pairs of integers, where each pair describes a connection between stars in the current group. Star numbering starts from zero.

Output

For each test, output 1 if you have an answer for this test, or 0 if you do not.

If you have an answer, the output file should contain K lines, where each line describes the corresponding sought constellation (in the same order as in the input data).

The line should contain -1 if the constellation is not found, or $N_i$ numbers of stars from the celestial sphere that form the current constellation. The stars should be listed in an order that satisfies the initial description of the connections of the sought constellation.

Examples

1
3
4 4
0 1 1 2 2 3 3 0
3 3 
0 1 1 2 2 0
4 3
0 1 0 2 0 3
7 7
0 1 1 4 1 2 2 3 3 5 3 6 5 6

1
-1
3 5 6
1 0 2 4