Sauce Circle - Repovive Premier Round 8 | Repovive

24B. Sauce Circle

1000 pts2s256 MB

There are $n$ dishes, numbered from $1$ to $n$ , and $m$ types of sauce, numbered from $1$ to $m$ . Dish $i$ needs exactly two different sauces, $a_i$ and $b_i$ .

Arrange all the dishes around a circular table so that, for every sauce, all dishes that need it occupy consecutive positions around the table. This consecutive part may wrap around the end of the printed order, and it may include the entire table. A sauce that no dish needs imposes no restriction.

Several dishes may need the same pair of sauces.

Find a suitable order of the dish numbers, or report that no such order exists.

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$2 \le m \le 2 \times 10^5$
$1 \le a_i,b_i \le m$
$a_i \ne b_i$
The sum of $n$ over all test cases is at most $2 \times 10^5$ .
The sum of $m$ over all test cases is at most $2 \times 10^5$ .

Input

t

\left. \begin{array}{l} n \quad m \\ a_1 \quad b_1 \\ a_2 \quad b_2 \\ \vdots \\ a_n \quad b_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} \mathrm{answer} \end{array} \right\} \times t

For each test case, $\mathrm{answer}$ is either $-1$ if no suitable order exists, or a permutation of $1,2,\ldots,n$ describing the dishes in clockwise order around the table. Any suitable order is accepted.

Samples

Input

Case 1

Case 2

Explanation

Case 1

In the order $4,1,7,5,2,6,3$ , the dishes needing sauce $1$ form the consecutive circular part $3,4,1,7$ . Those needing sauce $2$ form $1,7,5,2$ , and those needing sauce $3$ form $2,6,3$ . Each remaining sauce is needed by one dish.

Case 2

Dishes $1,3,5$ must form one consecutive part because they all need sauce $1$ . Whichever of these three dishes is in the middle has both neighboring positions occupied by the other two. However, it must also be next to dish $2$ , $4$ , or $6$ , respectively, because of its other sauce. This is impossible.

Output

Case 1

4 1 7 5 2 6 3

Case 2

-1

Input

Case 1

Case 2

Case 3

Explanation

Case 1

Every dish needs sauce $1$ , so its consecutive part is the entire table. The two dishes needing sauce $2$ are next to each other. Sauces $3$ and $4$ are each needed by one dish.

Case 2

Sauces $1$ , $2$ , and $3$ require dishes $1$ and $3$ , dishes $1$ and $2$ , and dishes $2$ and $3$ to be adjacent, respectively. Three dishes cannot all be pairwise adjacent around a table with four dishes, so there is no suitable order.

Case 3

In the shown order, the three dishes needing sauce $2$ occupy the first three positions, and the two dishes needing sauce $6$ occupy the last two positions. Every other sauce is needed by one dish.

Output

Case 1

1 3 2 4

Case 2

-1

Case 3

1 3 2 4 5

There are $n$ dishes, numbered from $1$ to $n$ , and $m$ types of sauce, numbered from $1$ to $m$ . Dish $i$ needs exactly two different sauces, $a_i$ and $b_i$ .

Several dishes may need the same pair of sauces.

Find a suitable order of the dish numbers, or report that no such order exists.

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$2 \le m \le 2 \times 10^5$
$1 \le a_i,b_i \le m$
$a_i \ne b_i$
The sum of $n$ over all test cases is at most $2 \times 10^5$ .
The sum of $m$ over all test cases is at most $2 \times 10^5$ .

t

\left. \begin{array}{l} n \quad m \\ a_1 \quad b_1 \\ a_2 \quad b_2 \\ \vdots \\ a_n \quad b_n \end{array} \right\} \times t

\left. \begin{array}{l} \mathrm{answer} \end{array} \right\} \times t

Every dish needs sauce $1$ , so its consecutive part is the entire table. The two dishes needing sauce $2$ are next to each other. Sauces $3$ and $4$ are each needed by one dish.

In the shown order, the three dishes needing sauce $2$ occupy the first three positions, and the two dishes needing sauce $6$ occupy the last two positions. Every other sauce is needed by one dish.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

24B. Sauce Circle

Constraints

Input

Output

Samples

24B. Sauce Circle

Constraints

Input

Output

Samples