F. Beautiful Intervalstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou 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.InputThe 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$$$.OutputFor 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.ExampleInput53 11 23 51 11 22 22 22 34 51 22 33 41 14 45 43 51 12 44 44 21 32 4Output2 0 12 1 0 0 2 1 3 2 0 1 3 4 3 1 0 2NoteFor 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$$$.