F. Beautiful Intervals
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an integer $$$n$$$ and $$$m$$$ intervals. Each interval is of the form $$$[l_i, r_i]$$$ and satisfies $$$1 \le l_i \le r_i \le n$$$. Note that there can be duplicate intervals.

Let $$$p$$$ be a permutation of length $$$n$$$ containing all the integers $$$0,1,2,\dots,n-1$$$ exactly once.

There is a multiset $$$M$$$ which is initially empty.

For each interval $$$[l_i, r_i]$$$:

  • consider the subarray $$$p[l_i \dots r_i]$$$,
  • compute $$$v_i = \operatorname{mex}$$$$$$^{\text{∗}}$$$$$$(p[l_i \dots r_i])$$$,
  • insert $$$v_i$$$ into $$$M$$$.

After processing all the intervals, $$$M$$$ will be equal to $$$\{v_1, v_2, \dots, v_m\}$$$.

Your task is to construct a permutation $$$p$$$ of length $$$n$$$ containing all the integers $$$0,1,2,\dots,n-1$$$ exactly once such that $$$\operatorname{mex}(M)$$$ is minimized.

$$$^{\text{∗}}$$$$$$\operatorname{mex}(a)$$$ denotes the minimum excluded (MEX) of the integers in $$$a$$$. For example, $$$\operatorname{mex}([2,2,1])=0$$$ because $$$0$$$ does not belong to the array, and $$$\operatorname{mex}([0,3,1,2])=4$$$ because $$$0$$$, $$$1$$$, $$$2$$$, and $$$3$$$ appear in the array, but $$$4$$$ does not.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. Description of each testcase follows.

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$3 \le n \le 3000$$$, $$$1 \le m \le 3000$$$).

The next $$$m$$$ lines each contain two space-separated integers $$$l_i, r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) each denoting an interval.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3000$$$, and the sum of $$$m$$$ over all test cases does not exceed $$$3000$$$.

Output

For each testcase, print a permutation $$$p$$$ of length $$$n$$$ containing all the integers $$$0,1,2,\dots,n-1$$$ exactly once such that $$$\operatorname{mex}(M)$$$ is minimized.

If there are multiple answers, you may print any one of them.

Example
Input
5
3 1
1 2
3 5
1 1
1 2
2 2
2 2
2 3
4 5
1 2
2 3
3 4
1 1
4 4
5 4
3 5
1 1
2 4
4 4
4 2
1 3
2 4
Output
2 0 1
2 1 0 
0 2 1 3 
2 0 1 3 4 
3 1 0 2
Note

For the first testcase, if we choose to construct $$$p = [2, 0, 1]$$$, then $$$M = \{\operatorname{mex}(2, 0)\} = \{1\}$$$. Now, $$$\operatorname{mex}(M) = 0$$$.

For the third testcase, if we choose to construct $$$p = [0, 2, 1, 3]$$$, then $$$M = \{\operatorname{mex}(0, 2), \operatorname{mex}(2, 1), \operatorname{mex}(1, 3), \operatorname{mex}(0), \operatorname{mex}(3)\} = \{1, 0, 0, 1, 0\}$$$. Now, $$$\operatorname{mex}(M) = 2$$$.

For the fourth testcase, if we choose to construct $$$p = [2, 0, 1, 3, 4]$$$, then $$$M = \{\operatorname{mex}(1, 3, 4), \operatorname{mex}(2), \operatorname{mex}(0, 1, 3), \operatorname{mex}(4)\} = \{0, 0, 2, 0\}$$$. Now, $$$\operatorname{mex}(M) = 1$$$.

For the fifth testcase, if we choose to construct $$$p = [3, 1, 0, 2]$$$, then $$$M = \{\operatorname{mex}(3, 1, 0), \operatorname{mex}(1, 0, 2)\} = \{2, 3\}$$$. Now, $$$\operatorname{mex}(M) = 0$$$.