Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

There is a chessboard with $N$ rows (numbered $1$ through $N$) and $N$ columns (numbered $1$ through $N$). $M$ squares on this chessboard (numbered $1$ through $M$) are marked. For each valid $i$, the $i$-th of the marked squares is in the $r_{i}$-th row and $c_{i}$-th column.

You should perform the following process:
First, you take a rook and put this rook on one of the marked squares.
Then you move the rook $M-1$ times; since it is a rook, each of these moves must be to a marked square in the same row or the same column as the square where the rook was currently standing.
The rook must visit each of the marked squares exactly once. In each move, squares strictly between those where the rook stands immediately before and after this move are not visited by the rook.
Also, the directions of the moves must alternate ― you may not move the rook in the same row twice or in the same column twice in any two consecutive moves.

Find one valid path for the rook that visits the marked squares. It is guaranteed that at least one such path exists. If there are multiple solutions, you may find any one of them.

------ Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $N$ and $M$.
$M$ lines follow. For each valid $i$, the $i$-th of these lines contains two space-separated integers $r_{i}$ and $c_{i}$.

------ Output ------
For each test case, print a single line containing $M$ space-separated integers ― the indices of marked squares in the order in which the rook should visit them. These integers should form a permutation of $1, 2, \ldots, M$.

------ Constraints ------
$1 ≤ T ≤ 10$
$1 ≤ N, M ≤ 50,000$
$1 ≤ r_{i}, c_{i} ≤ N$ for each valid $i$
all marked squares are distinct

------ Subtasks ------
Subtask #1 (10 points): $M ≤ 15$

Subtask #2 (90 points): original constraints

------ Example Input ------

2
2 4
1 1
1 2
2 1
2 2
1 1
1 1

------ Example Output ------

1 3 4 2
1

见题面

见题面