AT_arc200_c [ARC200C] Movie Theater

You are given a positive integer $ N $ and sequences of positive integers of length $ N $ : $ L=(L_1,L_2,\ldots,L_N),R=(R_1,R_2,\ldots,R_N) $ . It is guaranteed that $ L_1,L_2,\ldots,L_N,R_1,R_2,\ldots,R_N $ are all distinct. A movie theater has $ N $ seats arranged in a row from left to right. The $ i $ -th seat from the left is called seat $ i $ . $ N $ people, numbered $ 1 $ to $ N $ , visit this movie theater. You assign one seat to each person. Let $ P_i $ be the seat assigned to person $ i $ . Then, person $ i $ arrives at time $ L_i $ , crosses seats $ 1,2,\ldots,P_i-1 $ to sit in seat $ P_i $ , and leaves at time $ R_i $ , crossing seats $ 1,2,\ldots,P_i-1 $ to exit. The **dissatisfaction** of person $ i $ is the number of times other people cross seat $ P_i $ during the time interval from time $ L_i $ to time $ R_i $ (not including exactly $ L_i $ and $ R_i $ ). Find the lexicographically smallest permutation $ P $ of $ (1,2,\ldots,N) $ that minimizes the total dissatisfaction of all people from $ 1 $ to $ N $ . You are given $ T $ test cases, so find the answer for each.

The input is given from Standard Input in the following format: > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ Each test case is given in the following format: > $ N $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ \vdots $ $ L_N $ $ R_N $

Output $ T $ lines. The $ i $ -th line should contain the lexicographically smallest permutation $ P $ of $ (1,2,\ldots,N) $ that minimizes the total dissatisfaction of all people from $ 1 $ to $ N $ for the $ i $ -th test case, separated by spaces.

### Sample Explanation 1 For the first test case, if we set $ P=(2,1,3) $ , the process proceeds as follows: - Time $ 1 $ : Person $ 1 $ sits in seat $ 2 $ . - Time $ 2 $ : Person $ 2 $ sits in seat $ 1 $ . - Time $ 3 $ : Person $ 2 $ leaves seat $ 1 $ . - Time $ 4 $ : Person $ 3 $ sits in seat $ 3 $ . Person $ 1 $ 's dissatisfaction increases by $ 1 $ . - Time $ 5 $ : Person $ 1 $ leaves seat $ 2 $ . - Time $ 6 $ : Person $ 3 $ leaves seat $ 3 $ . The total dissatisfaction of all people in this case is $ 1 $ . It is impossible to make the total dissatisfaction smaller than $ 1 $ , and furthermore, $ P=(2,1,3) $ is lexicographically smallest among all $ P $ with total dissatisfaction of $ 1 $ . Therefore, $ P=(2,1,3) $ is the answer. For the second test case, the total dissatisfaction of all people is $ 6 $ for any permutation $ P $ . ### Constraints - $ 1\le T\le 500 $ - $ 1\le N\le 500 $ - $ 1\le L_i < R_i\le 2\times N $ - $ L_1,L_2,\ldots,L_N,R_1,R_2,\ldots,R_N $ are all distinct. - The sum of $ N $ over all test cases is at most $ 500 $ . - All input values are integers.