C - Movie Theater Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 700 点

問題文

正整数 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 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 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 以下
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

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 のうち辞書順最小のものを半角スペース区切りで出力せよ。

入力例 1

3
3
1 5
2 3
4 6
4
1 5
2 6
3 7
4 8
6
6 10
2 11
7 8
1 9
3 4
5 12

出力例 1

2 1 3
1 2 3 4
2 4 1 5 3 6

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 となります。

Score : 700 points

Problem Statement

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.

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.

Input

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

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 Input 1

3
3
1 5
2 3
4 6
4
1 5
2 6
3 7
4 8
6
6 10
2 11
7 8
1 9
3 4
5 12

Sample Output 1

2 1 3
1 2 3 4
2 4 1 5 3 6

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.