AT_arc200_c [ARC200C] Movie Theater

正整数 $ N $ と長さ $ N $ の正整数列 $ L=(L_1,L_2,\ldots,L_N),R=(R_1,R_2,\ldots,R_N) $ が与えられます。ここで、 $ L_1,L_2,\ldots,L_N,R_1,R_2,\ldots,R_N $ は全て互いに異なることが保証されます。 ある映画館には $ N $ 個の席が左右一列に並んでいます。左から $ i $ 番目の席を席 $ i $ と呼びます。 この映画館に人 $ 1 $ から人 $ N $ までの $ N $ 人の人が訪れます。あなたは各人に席を $ 1 $ つずつ割り当てます。人 $ i $ に割り当てた席を $ P_i $ とすると、人 $ i $ は時刻 $ L_i $ に席 $ 1,2,\ldots,P_i-1 $ を横切って席 $ P_i $ に座り、時刻 $ R_i $ に席 $ 1,2,\ldots,P_i-1 $ を横切って席から離れます。 人 $ i $ の **不満度** を時刻 $ L_i $ から時刻 $ R_i $ までの間（ちょうど $ L_i,R_i $ は含まない）に他の人に席 $ P_i $ を横切られた回数とします。 人 $ 1 $ から人 $ N $ までの $ N $ 人の不満度の総和が最小となる $ (1,2,\ldots,N) $ の順列 $ P $ のうち辞書順最小のものを求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ \vdots $ $ L_N $ $ R_N $

$ T $ 行出力せよ。 $ i $ 行目には $ i $ 番目のテストケースについて、人 $ 1 $ から人 $ N $ までの $ N $ 人の不満度の総和が最小となる $ (1,2,\ldots,N) $ の順列 $ P $ のうち辞書順最小のものを半角スペース区切りで出力せよ。

### Sample Explanation 1 $ 1 $ つ目のテストケースについて、 $ P=(2,1,3) $ とすると以下のように進みます： - 時刻 $ 1 $ ：人 $ 1 $ が席 $ 2 $ に座る。 - 時刻 $ 2 $ ：人 $ 2 $ が席 $ 1 $ に座る。 - 時刻 $ 3 $ ：人 $ 2 $ が席 $ 1 $ から離れる。 - 時刻 $ 4 $ ：人 $ 3 $ が席 $ 3 $ に座る。人 $ 1 $ の不満度が $ 1 $ 増える。 - 時刻 $ 5 $ ：人 $ 1 $ が席 $ 2 $ から離れる。 - 時刻 $ 6 $ ：人 $ 3 $ が席 $ 3 $ から離れる。 この際の全員の不満度の総和は $ 1 $ です。 不満度の総和を $ 1 $ より小さくすることはできず、さらに $ P=(2,1,3) $ が不満度の総和が $ 1 $ となる $ P $ のうち辞書順最小です。したがって、 $ P=(2,1,3) $ が答えとなります。 $ 2 $ つ目のテストケースについて、どのような順列 $ P $ に対しても全員の不満度の総和は $ 6 $ となります。 ### 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 $ は全て互いに異なる - 全てのテストケースにおける $ N $ の総和は $ 500 $ 以下 - 入力される値は全て整数