CF2162F Beautiful Intervals

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.

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 $ .

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.

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 $ .